Yes, it's dependant on location. His armor should be obtainable in the Razril area (which I haven't gotten yet) and his pirate outfit from Iluya. Basically you can dress him in any outfit that he appears in the course of the game.

Equipping a Champion orb will turn off encounters with weaker random encounters. It's possible to max out levels without too much difficulty with Reinhold (if you use Ted and a Mother Earth Rune). With a level 99 party, you effectly eliminate random encounters.

You can get one as early as Iluya Island (there's a treasure map in a chest there). Using that map Rene can locate a Champion Orb on one of four possible islands.