Level 3 Key Spheres can be mass-stolen from Biran and Yenke on Mt. Gagazet. You can also get one from the Chocobo Race in the Calm Lands.
Level 4 Key Spheres... you get one in Al Bhed Home, one in a chest on Mt. Gagazet and another one (two if overkill) from Seymour Flux.

About places you can go with the airship, you can find three by password. These passwords are hidden across Spira (since i don't have the english version, i can't tell you what they are). The places you unlock have chests with an armor for Rikku, a weapon for Auron and Rikku's celestial weapon.
With coordinates, you can unlock six (?) locs: Temple Baaj, some place in Besaid (only a treasure chest), Sanubia Desert, Mi'ihen Ruins, Mushroom Rock Road Battlefield and Omega Ruins.
Additionally, you can unlock the location "Penance" if you play the PAL/INT version and defeat all Dark Aeons.

And yes, you can get the item in the Aurochs' locker room later on.

Btw, if you go back to Omega Ruins after defeating Omega Weapon and go all the way back to where Omega was, you find a stat sphere. Magic+4 Sphere, I think.

Hint for Blitzball: Get Brother (flies the airship), Wedge (guard of Luca stadium), Kyou (masked man at the path to Djose Temple) and Myu or whatever (s)he was called (sitting on the bench at Moonflow North). Maybe Neda from the Calm Lands Shop for defense. These are so damn good players.