[X] Pewter City - Generally considered the starter city for gym trainers, the highest challenge it can provide is a 5-badge fight, but there's no rule saying it can't hold an 8-badge fight. It would take two weeks to travel there, however.
[X] Cinnabar Island - A large island with a gym, the leader is rather eccentric which makes it difficult for even experienced trainers. However, a migration of Skarmory is in the area which isn't a common occurrence.