To travel with NPC if very easy, just make a dialogue: 'hi', 'travel', 'yes'.
NPC Tracey: Pallet (Kanto) to Hamlin (Orange Islands)
NPC Aviator: Cerulean (Kanto) to Mandarin (Orange Islands).
Between Orange Islands there are many Nurse Joy who make routes between the islands, and also, in Kanto some places have motorcycles available.

How to get to Orre (Phenac/Agate):

From the Trovitopolis's pokémon center (Located on the mandarin island), head northeast. You will find the stairs to the subway, which will take you to the Orre Region.