Depends on your musical taste, which order to go in. You may want to start with "Chasing Time", which is a best-of compilation that covers albums up to Inside Out. That being said:
If you lean more towards Power, back track a bit. If you're more into Prog, move forward in the order of release. Here's a list with a brief description of each which will hopefully help:
Night on Bröcken (1984) - Iron Maiden influence is definitely there
The Spectre Within (1985) - Finding more of their own sound - some consider this their first real progressive-metal release with more complex song structures. Goes well with early Queensryche.
Awaken the Guardian (1986) - Frank Aresti replaces Victor Arduini on guitar. Some reviewers consider this one to be a Grandaddy of Progressive Metal.
No Exit (1988) - Ray Alder replaces John Arch on vocals. Not much of a departure, musically, from AtG... heavy and dark. 21 minute The Ivory Gate of Dreams in three letters - OMG
Perfect Symmetry (1989) - Mark Zonder replaces Steve Zimmerman on drums. Kevin Moore appears on keys. More complex drumming is evident throughout. Overall a much more sophisticated approach/sound.
Parallels 1991 - Many consider this one to be the most "commercial" album, though I don't consider Fates commercial.
James LeBrie guests on Life in Still Water. I consider this one a perfect halfway point between PS and APSOG.
Inside Out (1994) - I consider this one their most commercial. Not quite as strong as Parallels, but in a very similar vein. Monument is an awesome, awesome track.
A Pleasant Shade of Gray (1997) - Frank Aresti leaves, Joey Vera replaces Joe DiBiase on bass. Kevin Moore has a much more prominent appearance, though not overwhelming. This album is one song broken down into 12 parts with the introduction of some industrial elements. Many consider this to be their masterpiece to date, myself included.
Disconnected (2000) - Still Remains. No need to say anything more, just get it and listen.
X (2004) - Not your typical Prog. The complexity, in my opinion, comes from how subtle the complexity really is. Handful of Doubt has become one of my very favorite FW songs, as has Wish. Both slower, but both exquisitely beautiful.
As for ordering, check out Metal Blade, Laser's Edge and Amazon.
Hope that helps and I'll get some vendor links for you.