A few things.
One, I hope they shift the locations of several pokemon. Houndour needs to get their butts back over to Johto someplace (I could see them being found after Ecruteak, or maybe just before arriving there for the first time). The Growlithe and Vulpix (versions exclusives still, probably) can stay in the same places. What I'd really like to see are the Mareep earlier (especially if someone has the bright idea of giving Falkner a Skarmory).
Natu should also be easier to get to, I mean, there aren't that many Johto birds that are that great. At least this one does something different compared to Hoothoot, Skarmory, and Pidgey.
Togepi? Yeah, having one of those from that mystery egg would be a good idea to keep around. Those things are finally useful nowadays, after all.
Odd Egg: I think a random pokemon would be best, not just the baby forms of what you could find then and these days. This thing could set you up for a while if it's the right pokemon. But have the game mechanic figure it out as soon as you step foot outside of New Bark Town- that should either piss people off to the point that they won't start over, or someone's gonna have a lot of patience.
I think that the elemental stones would continue to be sold in Celadon City. However, I could see there being some form of 'home shopping channel' that could have various goods available to be purchased via PokeGear phone, which would take two or three days to arrive (in real time, of course). This would give you an intermediate stage between depending on random trainer generosity and after the E4. Could also be another way to get access to Revives earlier than you normally would, too. Just a thought, there.