Depends what your into, if you can give us a hint ie GA, Military, Commercial then I can recommend some things.

Ok-
GA-Anything by Carendo, or the Real Air Scout Package or SIA Marchetti, Flight 1 stuff ( Eg Pilatus, A36, Cessna 172).

Commercial- For excellent exterior models, go CLS. For the VC's go PMDG ( 737,747). Level D 767 is amazingly accurate, you've got Dreamfleets 727, the Flight1 Super 80. There are also some big packages, Like Aerosims Classic Jets package, or the Overland Package, which has a lot of aircraft! You might also like the CaptainSim 757, but there isn't a freeware panel for it yet and the systems aren't as complicated as PMDG or LDS, or theres the Captain Sim 727 or 707 if you prefer old jets. There are also a lot of products published by Just Flight, such as the 777 professional.

Commuter- PMDG Beech series is nice ( More models in C package but more liveries in the D package), Flight1 ATR 42-500, or the Eaglesoft buisiness jets are good.

International Airports-FlyTampa's stuff is good, especially things like Vienna LOWW. For the UK, Garry Summons UK2000 scenery is very good value for money, and his latest release, Gatwick Pro is really impressive. Also some of the Aerosoft stuff is good, I really like Frankfurt. Cloud 9 do a nice Amsterdam Schipol and LAX,

GA Airport- Again, Garry Summons UK2000 comes with a lot of stuff, or you might want to look at Aerosoft Lukla package as thats something different.

Some different aircraft, CaptainSim C-130 is amazing if your system can handle it, the Realair Spitfire is a dream, or something from Shockwave.

This is not a list of all the best stuff, This is just a list of the stuff that I mostly own that I think are outstanding. Anyone else can feel free to add anything they want, and I hope this is of some use Alex , If you want I can add some links?
Cheers
John.

Sir_Jon,how could you forget Aeroworx and its amaizing

Super KingAir B200!?

My first and favorite. Eaglesoft DG produces some of the nicest Busness Jets on the market.

For weeks I just couldn't stop flying the Citation X, and now even wth all my Canerado in my hanger, I still usually fly the Cirrus SR20G2

Cheers
Cameron

Commercial:
Dreamfleet 727
Flight 1/Cool Sky Super 80
PMDG 747

727 and Super 80 are more affordable at $35 each. 747 is more expensive at $55.

If I was to pick one I'd go with the 727, I personally like classic airliners.

PMDG 737NG.....I bought it a couple of days ago

Excellent lighting and really detailed FMC, just look at the VC night lighting!!!!
http://www.simviation.com/cgi-bin/yabb/YaBB.cgi?board=paywareshots;action=displa...
On the military side of things, i'd say LAGO Tornado or F16.

GA, I would go anything by carenado!

.Mic

Commercial - I echo the PMDG planes. You're not just getting fine models and virtual cockpits. You're also getting a bunch of systems particulary FMC and the intruments PFDs/E
ICAS very well done. LDS767 is good too but ticked me off they didn't include even a basic set of SIDS/STARS for their FMC when it came out.
Flight1 ATR-72 for commuter prop. ATR itself was involved with the Flight1 development.

GA - Carenado as well. 182RG my favorite. Makes the default look like an 8-bit cockpit. Echo Eaglesoft's jet. I just have one Citation CJ1 and lots of fun.

Terrain - Ultimate Terrain(it now includes USA roads as well, and night light textures , freeway lamps etc.)

Sky - Flight Environment

Airports - Imaginesim or later FlyTampas

Commercial Traffic - Ultimate Traffic. 2003 real world traffic but real world flights imo don't deviate all that much in 10 years. Traffic 2005 was dissapointing to me.

ATC/ Crew flows:  Radar Contact v4, and FsCrew for PMDG 737.

Must haves: ActiveSky6(dynamic weather based on real METARs plus extra nice cloud and weather textures), and ActiveCamera(for the interior mouse panning and inertial effects). Radar Contact V4(only if you want serious "annoying" realistic ATC simulation, if you bust an altitude you get "reported" and probably fined irl, see the review on avsim.com, but lousy taxiing directions - just "missing". ).

Books: Mike Ray's books. He's a former 747-400 UAL pilot/captain among other boeings he's flown. His illustrative style is cartoonish but entertaining and enthusiastic about the wonder of FS for PC's today. But make no mistake , lots of serious material explained and
well illustrated.

Historic: sorry, I'm not really a historic or military sim-flyer. Heard from a friend Falcon 4.0 is excellent but not part of FS2004.


Comments on payware vs. non-payware: imo payware has gotten a lot better in the past two years. It's now real business with full time development into it and not just part-time or hobby work. I had tried freeware/shareware before diving in payware and today there is hardly a case for comparison that is if you compare the excellent paywares and avoid the turkeys.