The original progressive death metal band was Nocturnus, check out their 2nd album 'Thresholds'. If you don't mind death vox then you'll love this album, the guitar work is incredible - two very musical shredders and they also had a keyboard (shock horror! - remember this was about 15+ years ago). They were way ahead of their time and didn't really make it big because at the time most guys thought having keyboards in metal was 'gay' or something - total pity because this band really kicked ass. If you like Thresholds then you should also check out their debut 'The Key'.
Another equally talented and more pgressive DM band is Cynic (although their latest release is not DM at all). Check out their debut 'Focus' it's noted for being one of the best undergound metal albums of all time. As far as other heavier bands go you could check Atheist 'Unquestionable Presence', Pestilence 'Possessed' and anything by Death from Spiritual Healing on (one of the best Death albums was 'Human' - Chuck was backed up by the guys from Cynic on this recording).
The last two Symphony X albums are excellent, plus you could check out Spiral Architect's 'Sceptics Universe'. Never really liked Dream Theatre, the singer does nothing for me and I think Petrucci sounds so much better in his instrumental prog band Liquid Tension Experiment. Queen were very prog at the time and their stuff still rocks,