On top of what's been mentioned, how about the following...
'Another Day': A good one for both rhythm and lead, and the solo would be a good primer for some of Petrucci's more intense stuff.
'Surrounded': As above, and if he's into extreme delay effects (like me!
) the solo is an absolute blast!
'The Silent Man': This is a great exercise in acoustic rhythm playing, and it means he'll always have a song tailor made for open-mic nights in his repetoire (I used to play this one with a female friend back in school, with her singing and me playing guitar).