Gospy: EU3! If you can handle its complexity, it's so so so so so much fun. Check out the thread
here, Daer walks us through the early part of a game in
this post.
Playing max speed all the time is an awful idea, you'll just lose because the AI isn't making decisions as slowly as you are during wartime. It's definitely not an RTS in the SC2 style but Gospy did say he likes Total War iirc so that would seem to indicate he can handle non-SC2-like strategy games.