(when you haven't seen a single episode of the show)
thefourthvine has written a charming overview, Fandoms I Have Loved 10: Stargate: Atlantis, which will tell you everything you need to know about the background of this series in order to dive into the fic.
She also gives five starting recs, which are good, but not the ones I'd choose. So here's my alternate selection:
- The Rising by miss_porcupine (No Pairing, PG)
This offers a well-characterised re-telling of the start of the Atlantis story, introducing all the major characters and giving a good feel for the general background. This author is prolific and highly readable.
- Retrograde Series by ltlj (No Pairing, PG-13; final chapter McKay/Sheppard/Emmagan, R)
Another long, plotty mostly-gen story that gives an excellent feel for the Stargate universe. Again, the author is prolific and very readable.
ETA: See, I was sick when I wrote this up and I forgot to mention something. I picked this story as number 2 because it crosses over with the SG1 team (which means the story has some AU elements, as that hasn't happened in canon). So it's a great introduction to Atlantis if you're at all familiar with the original Stargate series. If you're not, move on to the next story, and come back to this once you've finished the list. Okay? Okay.
- Intersections by kaneko (McKay/Sheppard, NC-17)
This one is a fantastic introduction to the main slash pairing of the fandom (in fact the main pairing full stop): John Sheppard and Rodney McKay. It's set right at the start of the series, so it doesn't require canon knowledge, and it's long and detailed and beautifully written.
- Small Primes and Square Roots: Part 1, Part 2 by liviapenn (McKay/Sheppard, R)
AUs are a good introduction to a fandom, because they don't rely too heavily on canon knowledge, but still give the reader a grounding in the characters. This is possibly the most adorable AU in the whole fandom.
- Hindsight by rageprufrock (McKay/Sheppard, R)
This is one of the most influential AUs written in the fandom to date. Pru is another prolific, highly readable author.
- No Refunds or Exchanges by astolat (McKay/Sheppard, NC-17)
This is slightly AU, so it can be enjoyed whether you know canon or not. It's a wonderful riff on the marriage of convenience idea, and was written for the influential Harlequin Challenge over on sga_flashfic. This author is one of the biggest names in the fandom, and her stuff is hugely entertaining.
- Care in the Holding by laceymcbain (McKay/Sheppard, R)
This is not AU or gen, but by now you should be able to follow the broad strokes of the canon. I've picked this one because it's character-driven and focuses on the dynamics of the mission team as they go about their business within the city of Atlantis. It's also a favourite of mine.
- Looking for Lamour by trinityofone (McKay/Sheppard, PG)
Technically, this fits in with canon, but as it's a beautiful roadtrip set on earth, the canon isn't very important. trinityofone is another prolific, readable author. She has a real talent for writing amazing sf in this fandom.
- Scenes From A Lesser War: One, Two, Three by amireal (McKay/Sheppard, NC-17)
A classic of the post-Don't-Ask-Don't-Tell genre. amireal specializes in long, plotty stories, and they're all very enjoyable.
- Freedom's Just Another Word For Nothing Left To Lose: One, Two by synecdochic (McKay/Sheppard implied, PG-13)
This is probably the most famous story in the fandom, and it's beautiful.
ETA: jssangel points out that, I think a new fan might end up being cheated by reading [Freedom] too early. Part of why it was so moving to me was the depth of "history" I have with John and Rodney and all the different possible permutations of their relationship, which I think, in hindsight, is a good point. So if you'd like to hold off a little, and save this story up, here is an alternate rec:
- Eurydice Turns Left: one, two, three, four, five by vee_fic (No Pairing, PG-13)
This is a long, beautifully written mission-gone-bad story with a really strong Ronon (who doesn't feature much in the stories I've listed above, as he only arrived on the show in Season 2). It's a relatively recent story, and a new favourite of mine.
Okay, by now you should have a feel for the characters, so here are some more of the fandom classics:
ceteramisto has put together a love listing which includes links to many of the most famous stories in the fandom.
Now that you've read those, you can start in on the huge backlog of fantastic stuff.
thefourthvine's SGA recs are all worth a read, and there are many.
You can find a heap of recs for both SG-1 and Atlantis (mainly Atlantis) in the memories of rec_room. You can also search for just the Atlantis recs via tags. ETA: rec_room has moved to delicious now, so you'll find more recent recs there.
And once you've worked through those, you can start going through my list of reccers. The notes beside each link will tell you if they rec SGA.
You can find new stuff at sga_newsletter, which gives links to nearly everything published each day. There's also a Newbie Guide, which is chock to the brim with links to various SGA communities.
There's also the archives: Wraithbait, and Area 52.
ETA: I've started a trend!