optionally, ideas for the gym puzzle too.
Here's mine for example:
>Museum themed
>Relicanth represents "living fossils"
>Cofagrigus references ancient artifacts
>Unown references historical artifacts and literature
>Garchomp represents the transition from sea to land
>Archeops represents early avian ancestors
>Aggron represents Ceratopsidae and other dinosaurs
The gym puzzle would basically be a guided museum tour. You would have to get hints to go to certain museum exhibits in order. (Fossils, Art, Ancient relics, aquarium), all in a random order. In each exhibit, you would battle a gym trainer. After all 4, you face the gym leader in the back of the museum.