My thoughts:
1. Make Roost available to Empoleon, and Slack Off available to Snorlax.
Why: It creates some viable alternatives to Blissey for Special Walls. Blissey is overused because nothing else matches her.... these two simple switches would give us some alternatives to Blissey for a change. This is a change that could happen in the next cartridge for Gen 4... it doesn't have to wait. In the next Gen you can simply create new Special Walls to compete with Blissey.
2. Make Poison Super-Effective to Water, make Water Resist Dragon.
Why: This would have to wait until Gen 5, but it would make Water Types resurgent while still holding them in check. Water would resist dragons, and as most Water Types have access to an Ice Attack, the number of Dragon Counters would rise.
3. Lower the effectiveness of Evasion Enhancing effects.
Why: Easily changed by adjusting a math formula here or there in the program code, this would make Double Team and other moves relatively useless. That means we don't need the Evasion Clause. Evasion could still see use among players that want to "Play the Percentage", but the returns would be greatly diminished. Probably couldn't happen until Gen 5.
4. New Competitive Weather Effects, such as one keyed to Poison Types.
Why: Another attempt to increase the effectiveness of the Poison Type on my part. A "Poison Fog" weather type that acted negatively towards non-Steel, non-Poison Types, but had a "Leftovers Effect" for Poison types would go a long way towards helping out the type as a whole. This also would have to wait for Gen 5.
5. New and More Move Tutors to teach Elemental Punches, Fangs, Rapid Spin and other Utility Moves.
Why: In general, Utility Moves like Rapid Spin, Aromatherapy, Wish, etc, need to be passed around. More access to Elemental Punches and Fangs could help some pokemon. This could happen as early as the next Gen 4 Cartridge.
6. More Field Clearing Moves, or expand the usefulness of some moves by adding clearing obstacles or weather.
Why (And Specifics): Why doesn't Whirlwind Clear Spikes and Rocks? Why doesn't Defog clear Weather? Expanding existing moves to both clear weather and clear battle field obstacles would be a solid move on the part of Game Freak to help bring some control the the Sandstorm/Spikes/Rocks issues.