I'm only somewhat of a fan, but I can probably make some solid recommendations.
-Parallels, which came out in 1991, is I believe their most successful and is considered by many to be their best. You probably can't go wrong with this album. Not only is it pretty generally well-liked, but you'll likely hear quite a few songs played from it at your show since (1) it was their most successful, and (2) they just reissued it earlier this year and will likely play a lot of it to support the re-release. I would pick up the new version, as you get a lot of bonus content, including a live set. This is a great starting point for any Fates fan.
-They have a compilation/hits album called Chasing Time, which gives a pretty good sampling of their material from '84 to '94.
After the compilation album, they had another 3 releases. I only have the most recent, X, which came out in 2004. I get the impression it wasn't received all that well, but I like it a lot.