Thanks for the last post, Midnight.  It forces me to sharpen my thinking on a couple of points.

First, how could I forget phrenology?  (I've even had the privilege of being phrenologically analyzed!)  It shows up a lot in 19th century American literature.  Poe has it in some of his works.  I think some Whitman poems have allusions to it.  Twain wrote a debunking piece on it.  In fact, phrenology isn't totally a pseudoscience.  We now know there are localized areas of function in the brain.  It's just that the locations aren't where the phrenologists thought, the functions aren't divided the same way, and you can't spot the functions via skull bumps.

You make a good point about Poe's attitude toward phrenology's validity being, literarily speaking, irrelevant.  He knew his audience was interested in it, may have thought it a science, and might regard phrenology as being a rational indicator of character and capacity.  This is no different than a modern science fiction writer having aliens show up in a flying saucer.  A lot of science fiction writers have used that premise at one time or another, but, in their personal life, they aren't believers in UFOs as alien spaceships.  The UFO can be a fantastical conceit that elaborate extrapolations are made from.  However, I don't recall Poe ever using phrenology the same way, as a starting premise, "one impossible thing" he would carefully, realistically extrapolate a story from.

As to literary genre, maybe we might want to consider an imperfect analogy:  biologists trying to define what is a separate species and when it evolved from predecessors.  At some point, sometimes surprisingly arbitrary, you have to retroactively draw a line and say here is where a new species started.  And I think, if you're talking the history of science fiction, you can make a defensible case for Poe's work starting the genre.  And I don't think it's at all arguable that, if Poe didn't write science fiction, he contributed some literary genes to it.  For instance, it has been noted that "The Masque of the Red Death" inspired far future stories of decadence.

And I don't think it's at all coincidental that Poe stands at the beginning of two modern genres:  science fiction and mysteries.  The appeal of these stories to the reader can be similar.  Many science fiction stories are constructed as mysteries, but the mystery to be solved is one of the natural world or of history, not of crime necessarily.  Thus, one can build both types of story the same way:  start with an effect, the solution of the mystery, and then work backwards as to the clues that will be supplied to the reader.  And there is a fair number of crossover readers of these two genres.  Since the 1950s, they have been fruitfully combined on occasion.  (Isaac Asimov was actually a pioneer here.)  When you look at how Poe constructed his Auguste Dupin stories or how he claimed to have calculated the composition of "The Raven" backwards from his intended effect, its not at all surprising he pioneered both genres.  His mind was uniquely suited to constructing stories that way whether he developed the method because of his aesthetic theories or he rationalized his theories to account for the type of stories his brain produced.

And, in a way, Poe's suspension of rationality in "The Tell-tale Heart" or "The Cask of Amontillado" makes those stories more powerful.  What do I mean?  In the first tale, we know the narrator is mad however carefully he plots his crime.  Rational planning clashes with irrational motive.  You can say the story is a study of madness and character but that's a way of also saying it's about suspended rationality.  In "Cask", Poe has ommitted describing exactly what Fortunato has done.  Sure, that's because it's irrelevant what he's done.  This is a story about executing revenge.  But Poe's ommission of Fortunato's sins isn't just streamlining.  It's also ommitting a key detail virtually every other author would have included prior to Poe.  If the revenge story is a logical chain of described crime, suffering victim, plotted revenge, and executed revenge, Poe has left out the first part of the chain.

Maybe we should think of Poe as a writer who carefully considers the artistic uses -- both inclusion and strategic exclusion -- that rationality and its supporting narration of details can be put to.  Birthing two modern genres may just be part of a larger game Poe played. 

Perhaps Poe, when writing his more dream like pieces, didn't imagine his stories in full form.  Maybe the dreams were shaped by carving away rational bits in a quite deliberate way.  In other words, Poe's genius wasn't odd visions; it was turning reality into odd visions by manipulating the language and expectations of rationality. 

Poe as a calculating artist, a literary engineer and not a literary shaman channeling spirits shows up in "Ullalume".  It's a poem written, after all, as an elocution exercise.  His humor pieces point to a rational writer, not a channeler of dreams, since the humor relies on puns and carefully chosen names.  In fact, humor also seems a pretty calculating, however successful it is, literary exercise.  You have to set jokes up, build entire stories around punchlines rather than just meander.

At least, that's my half-baked thoughts on Poe today.

Midnight, I definitely stretched the definition of science fiction to include Pym and "MS. Found in a Bottle".  You could argue that a lot of elements of Poe were incorporated into science fiction from its primary form, the short story, to some of its concepts.  I got out Brian W. Aldiss Billion Year Spree:  The True History of Science Fiction and re-read the chapter on Poe.  (The chapter is titled "A Clear-Sighted, Sickly Literature" which comes from a quote about Poe by the Brothers Goncourt.)  He has a nice line about Poe's relation to science fiction.  Citing Poe and his Gothic forbears, Aldiss calls their work "cathedrals of an earlier age, whose stones were often appropriated for the hastier buildings of later ages."  The point being that Poe's elements didn't start out in the structure of science fiction stories.  For instance, "William Wilson" is about doppelgangers but it never really rationalizes the concept, never justifies with scientific or technological jargon.  However, later science fiction would rationalize the notion with the multiple-worlds interpretation of quantum mechanics, clones, and matter transmitters and duplicators.

Using a definition of science fiction as "a branch of fantastic literature that rationalizes it's fantastic elements with scientific, pseud0-scientific, technological, or pseudo-technological elements", I think some of Poe's works counts.  "Valdemar", while not one of my favorites, is one.  "Pfall" is one.  It's not one of my favorites either because I've read a fair number of those early "voyage to the moon" stories.  However, it has to be acknowledged that Poe went out of his way to rationalize his wonderous trip.  That's what makes it important.  It inspired Verne to make such efforts in describing his extraordinary voyages.  I have a suspicion, though I'll have to research it, that "The Conversation of Eiros and Charmion" inspired a couple of H. G. Wells works.  I think it probably stands close to the beginning of stories that imagine some apocalypse rationalized by astronomical theories.  Wells wrote one such story called "The Star".  More importantly, I think it may have inspired Wells' In The Days of the Comet -- his wishful thinking novel of social change via cometary gases.

Critic James Gunn argues that "Mellonta Tauta" is the first science fiction story.  It imagines future technology and, just as important, future social and linguistic change, a future quite different from the reader's.  I think it may have also inspired Wells' The Time Machine though, of course, Wells future vistas are much vaster. 

Poe was, of course, something of a hoaxer.  There is a little known thread of 19th century American science fiction that was produced, particularly in San Francisco, as newspaper hoaxes.  However, I can't tell how closely any of the writers were influenced by Poe.

Verne, of course, took up the mantle of Poe in a couple of ways.  As I said, one was carefully rationalizing his technology ala Poe's "Pfall", but I think another important similarity, whether intentional on Verne's part or not, was largely, like Poe, a reluctance to embrace didacticism.  Wells, of course, was both didactic and less scientifically plausible in his stories though I think a Poe influence possible.

Since you asked my favorite -- rather than the one I thought most influential or most innovative or most recognizably science fictional, I'd say "Ms. Found in a Bottle".  Partly that's due to the reflected glory of the story in Clark Ashton Smith's retelling in "The Uncharted Isle".  But I do like the atmosphere of the story.

I also like the The Narrative of Arthur Gordon Pym though more for the straightforward sea adventure rather than the mysterious ending.