It would be nice if instead of LEVEL UP = INSTANT ALL STAT PLUS, you like...made level ups less useful, and made it so you trained pokemon as if they were real. Like for stamina, you would take them to the pool and have them swim or something. Not only does this make the game a bit harder (in a good way) it makes things interesting, and it's a huge opportunity for mini-games.
To make it even MORE interesting, and to add incentive to beating the gym leaders, you could make it like say...Misty is at the water gym, and the only one with a public pool for miles around. You aren't a local resident (this goes back to what I said in the shadow topic about starting at a city based on a personality quiz- which he isn't useing by the way so the idea is up for grabs) you have to get her badge to use the pool.