I always take Cyan and Gau to the Empire. Gau's rages helped when I wanted to conserve MP, and Cyan's Quadra-Slam helped for the melee encounters.

Also, one of the best parts of the game in my opinion is when you go to the Empire, so have fun.