I'd be curious about the kinds of themes that Pokemon tries to go for - specifically the addictive, 'catch 'em all' thing - applied in a new way. Collecting and trading is a key mechanic of the series, and there's surely unique ways to go about that. Maybe instead of a rote checklist of things to catch, what about a game where they have a mix of pokemon - old, new, and freshly-created - and just don't tell you what they are, where to find them, or what they can do. It could be like you said, a primitive person in the pokeworld, or a kid who doesn't have a "professor oak" to get them on track. Either way, it would embrace more of a "thrill of discovery" kind of thing more than a simple, rote "fill out the list". Imagine just travelling around in a big, Skyrim-esque overworld brimming with hidden caves, deep lakes, and secluded forests, and you have no idea whats around the next bend in this savage, uncivilized world, like a pokemon madagascar or galapagos. You could catalogue all the new and thrilling species, and have to do more to learn about them than just catch it once - maybe engage it in combat, or stalk it to watch its habits, so you can really earn that 100% pokedex.
That would be really cool if there was also a procedural world generation so every experience is slightly different. Pokemon aren't in the same place for everyone, checklists might be different, certain Pokemon might be a little different, etc. I'm thinking of a cross of roguelike elements with Pokemon: like expanding the premise of the Pokemon Mystery Dungeon games.
Well, if you really wanted every experience to be different, you could use my absolute favorite algorithm ever. When the game starts you seed the environment with Pokemon, and have a loop running in the background which periodically makes a huge amount of quick battles happen, and then those (non-user) pokemon which beat other (non-user) pokemon get an appropriately large amount of the space they inhabit. In this way, you would actually see an automatic progression to more powerful pokemon, real evolution, and make it impossible for anyone to spoil the location or types for anyone else. I love the Genetic Algorithm so freaking much.
There could be all sorts of neat ways to implement the procedural content. While it might be harder with a GA, I was thinking that it might be neat to be able to share the seed. That way that people could, if they wanted to, play the same instance and share secrets for that instance. Kind of like the "password" system in the fictional .hack where 3 words seed the content so you can share the same zone between players and the WonderMail system in Pokemon Mystery Dungeon.
Great idea! Having a user-accessible seed for a GA seems like a great way to create a potentially "unique" but sharable experience! Man, I needa get this 2d physics engine finished.