I’d definitely add Vernor Vinge (recent novels: A Fire Upon the Deep and A Deepness in the Sky; also a book of short stories). Bujold has a recent fantasy series as well as the Vorkosigan books. Brust has books besides the Vlad Taltos series (including another series set in the same world, beginning with The Phoenix Guards).
How much shelf space do you have available?
Check Locus Online. They’re the trade magazine of the industry, sorta, and do a weekly combing of various bestseller lists of paperback f&sf as well as an annual review of the best of the year. They also run interviews with big names monthly or more frequently.
Just to mention some names who are currently writing and selling big that I think haven’t been mentioned: David Drake, S. R. Stirling, Laurell K. Hamilton, Catherine Asaro, Simon Green, Neil Gaiman, Terry Goodkind, Elizabeth Moon, J. D. Robb, Robert Sawyer, Kim Harrison, Robert Silverberg, Mike Resnick, Cory Doctorow, Charles Stross, Jack McDevitt.
And you just gotta have those newbies Stephen King and J. K. Rowling.
Speaking of Rowling, here’s a list of Harry Potter alternatives from the L. A. Public Library.
I gotta know: why, why, why, when you ask for the new names do people still mention Heinlein and Howard? (OK, I do know: it’s the same reason that people give names that are in the OP. 
)
I’d suggest Heinlein’s juveniles (Or, at least, Have Spacesuit, Will Travel), and LeGuin’s The Left Hand of Darkness be added to the list.
Also, I’m a big fan of Ted Sturgeon. More than Human might not sell, I consider that a fatal flaw of the basic soul of mankind.
Phillip K. Dick’s books are popular & I admit they’re a great read. I can’t recommend any of them in particular, though.
Recommending stuff that’s popular, I’d say David Brin, Lois McMaster Bujold, Orson Scott Card, Eric Flint, George R.R. Martin, Dan Simmons, S.M. Stirling, and Harry Turtledove.
I can! Definitely stock Do Androids Dream of Electric Sheep? and one of the best-of short fiction collections since movie buffs might be interested in reading the source material. A Scanner Darkly is one of his more popular novels and they’re making a movie of it, too. My personal very favorites are Martian Time-Slip, The Three Stigmata of Palmer Eldritch, and Valis, but they might not be as popular. The problem is, all of these are only currently published in trade and I don’t know how your customers feel about trade vs. mass market. When the ASD movie comes out, I’m sure there’ll be a mass market version of it (probably with a terrible movie cover, but still) and that might sell better. The trade covers are pretty horrible too, though.
Cory Doctorow’s first two novels (well, third too, but it’s hardback still) were totally amazing. Also in trade, though.
Thirding the vote for the Honor Harrington series of books by David Weber. This series has also recently branched off into a couple of new series (Crown of Slaves and the Saganami Island series), but neither branch has been developed much yet. Of course, if you stock the Honor Harrington books, be sure to get some Horatio Hornblower books for the regular fiction section, too 
Other than that, all I can really suggest that hasn’t been suggested already is your typical sci-fi staples (ie: Star Wars books). Maybe you can encourage folks who start to walk out of your store empty-handed if there are any books in particular they’re looking for. You can always special order them, and if you notice a trend for a particular author or series, that will give you an idea of what to look for in the future.
Seconding Charles De Lint and Sheri Tepper.
I also really like Guy Gavriel Kay. His Fionavar Tapestry was just republished.
Greg Egan is worth a look.
I’d also recommend stocking compilations of short stories, but only because this is what I personally buy most of.
More recommends for S.M. Stirling, David Drake, John Ringo, Eric Flint, Larry Niven, R.A. Heinlein (don’t discount the earlier stuff, either).
Maybe some of Glen Cook’s Black Company series.
Every bookstore I’ve been in (and I’ve been in a lot) stack the Turtledove alternate history novels in with science fiction. That’s where I usually find alternate histories, in ant case, and the World War series is both alternate history and science fiction.
Turtledove also does straight fantasy (“The Case of the Toxic Spell Dump”, “Conan of Venarium”) and science fiction (can’t recall the titles right now)
Someone above suggested L. Sprague de Camp and Poul Anderson, but most of their books (like Asimov’s) are out of print. I’d certainly suggest them as excellent books, but I don’t know how well known they are and how they’d sell today.
I think you should add some Jules Verne and H.G. Wells books, including a few of the less well-known ones (which are still in print). Everyone knows Verne and Wells.
I don’t know anything about your customer profile, or how much space or budget you have to devote to sf&f but here’s a list of 20 September/October new titles that I suggest you consider stocking.
I didn’t include any Star Wars/Star Trek/Dragonlance/Forgotten Realms/Mechwarrior/Games Workshop/etc. as I assume you have a handle on what to get along those lines…
Anderson & Herbert - Dune: The Battle of Corrin
Catherine Asaro - Schism
Carol Berg - Daughter of Ancients
Robert Buettner - Orphan’s Destiny
William Dietz - For Those Who Fell
Dave Duncan - Jaguar Knights
Eric Flint - Ring of Fire
Alan Dean Foster - Sliding Scales
David Gemmell - Hawk Eternal
Simon Green - Paths Not Taken
Laurell Hamilton - Incubus Dreams
Matthew Hughes - Black Brillion
Mercedes Lackey - Phoenix & Ashes
L E Modesitt, jr. - Sceptres
Elizabeth Moon - Marque and Reprisal
Terry Pratchett - Going Postal
S M Stirling - Dies the Fire
David Weber - The Shadow of Saganami
Walter Jon Williams - Conventions of War
Timothy Zahn - The Grey and the Green
You’ll notice that almost all of these are parts of series, btw.
Hope this is of some use…
I’ll definitely second the following;
Peter F. Hamilton
Stephen R Donaldson - the Gap series
Vernor Vinge
Dan Simmons
I’d recommend
Julian May - Pliocene Exile series, Intervention series, and Galactic Milieu series
I’ll recommend Sarah Zettel’s Fool’s War and Playing God, both of which are good, thought-provoking SF, one about artificial intelligence and one about intervening in the affairs of alien races.
It may be a bit hard to find, but if you can find it, Diplomatic Act by William H. Keith, Jr. and Peter Jurasik of Babylon 5 is also a hoot! It’s similar to Galaxy Quest but was written before it and is better. I should put in one disclaimer – Bill’s a very good friend of mine, but that doesn’t change my opinion of it.
CJ
I cna’t believe no one has mentioned the AD&D books. Weiss & Hickman are best sellers everytime they throw their name on a cover, and all of RA Salvatore’s books hit the million mark. Take a good look at how that entire product line is moving, and if you’re ruinning a smaller store you may be able to run some smaller event type dealies (host some games or have some extra mercandice around for the gaming crowd.) Also you might want ot look over at the Aspect lIne. ITs TIMe Warner Science Fiction line. I’m a bit partial to them, since i used to work there, and I’ll be the first to admit that most of their cover art blows but there are a few sleepers in there. Like Alison Baird’s the Stone and Stars and its sequal The Empire of the Stars are both great reads, though are in Trade paperback size. Dunno if they’ve been released in Mass Market yet. nd Checking on amazon, I’ve jsut noticed The Archons of the Stars the 3rd book int he seris is out and I MUst now make a call to my good friend to get a copy for free Good luck with updating your store though
For Hobb, you’ll definitely want the first Farseer trilogy–Assassin’s Apprentice, Royal Assassin, and Assassin’s Quest. I haven’t read the Liveship trilogy, but I’m told people like it.
Eddings’ Belgariad is a must: Pawn of Prophecy, Queen of Sorcery, Magician’s Gambit, Castle of Wizardry, and Enchanter’s End Game. The Malloreon is a second five-book series with the same characters that you may or may not want to pick up (Guardians of the West, King of the Murgos, Demon Lord of Karanda, Sorceress of Darshiva, Seeress of Kell). But you’ll definitely need the two stand-alones that go along with the series, Belgarath the Sorcerer and Polgara the Sorceress. Pure fun fantasy.
If you have a YA section, you should get Philip Pullman’s His Dark Materials trilogy, definitely Garth Nix’s Old Kingdom series (my husband says * Shade’s Children* is fantastic, too, and the Across The Wall anthology is nice), The Neverending Story, by Michael Ende, and maybe some Tamora Pierce. I’ve only read her Lioness Rampant series, but everything she writes is popular. Trickster’s Choice and Trickster’s Queen (I think) are pretty recent.
The Artemis Fowl books at my work sell pretty well.
Second The Left Hand of Darkness, but get The Dispossessed, too. And maybe The Birthday of the World. I think that’s her most recent book.
L. E. Modesitt jr.'s Magic of Recluce books are reasonably popular. They’re an okay read. He has quite a few novels, but I’ve only read the Recluce series. It’s about ten books long, I think.
You folks have given me a lot to look at, and yes, I’m going to go move Turtledove into the science fiction/fantasy section right away.
I don’t need any more young adult suggestions. As I mentioned in post #8, I have a separate young adult fantasy section which does well, and I think I have the Harry Potter, Eldest, Artemis Fowl, Spiderwick, and so on pretty well covered. It’s the general (adult) science fiction and fantasy where I need to expand.
I’m on top of the New York Times bestseller list, Captain Amazing, although it doesn’t tend to do nearly as well here as the Book Sense bestseller list.
I’ve checked out Locus Online before, Exapno Mapcase, but unless I’m missing something their bestseller list is just a compilation of other people’s lists. I didn’t find anything new on it, and it’s very heavily young adult.
Yes, Yookeroo, I checked out Amazon’s lists. It’s very heavily focused on new-release hardbacks, which don’t sell well here. It appears people buy different books online than they buy locally. Interesting phenomenon. Maybe I’ll start another thread about that.
Thanks again for all the suggestions! Keep 'em coming, folks.
Thanks for that suggestion. I’m actually a dealer for Wizards of the Coast, and we sell the AD&D rule books, Magic: the Gathering cards and accessories, and Forgotten Realms books. I tried running some D&D games here for a while, but it took too much time and energy for the return. There are only 2,300 people in this town, and for some reason the tourists don’t pick up those books.
I wish that just once, Wizards of the Coast would screw up and send R.A. Salvatore my Magic cards and send me his royalties 
Posted by InvisibleWombat:
What? They’re not interested in de Camp and Anderson? I guess the customer isn’t always right.
Well, with Baxter I haven’t read that much, but I really enjoyed Anti-Ice, The Time Ships and Voyage.
Has anybody mentioned Gardner Dozois and Bruce Sterling?