You can only hire one hireling at a time, so hiring a mage in mysidia means dismissing your ninja. They can be re-hired, but their stats are reset (like you are hiring a different person... Who just happens to have the same name
). You get to keep a dismissed mage's "spell book" though, so they come back with the same spells learned.
As for chocobos, there's nothing you can do at this stage of the game to make them easier to catch. They are more plentiful in forests than any other terrain, but they show up with "Old Trees," which have a lot of HP. When you inevitably get Palom in your party, one party-cast fire2 should do the trick - chocobos are immune to magic, so it won't get hit. Keep Palom in the center spot so he gets the first turn. Later in the game... Much later in the game, catching a chocobo will be required, but you'll have a character in your party (Kella, if you've read the OP) who is guaranteed to catch a chocobo if she attacks it with a whip.
I'll have to look into that shop issue, that's the first I've heard of it, so good catch. Thanks!
Thanks also for the feedback, I can't overstate how much it helps to have people actually play the game