New pokemon? Not unless they are incredible, like the ones planned for Pokemon Crono, those look amazing.
New Region? Definitely. I'm tired of remakes. SS was amazing but largely due to the pokemon following mechanic, most hack remakes are just plain unnecessary.
New Type? Definitely not. Not needed at all.
New Attacks? Maybe, if you can make them look good. If you just slap in the same animation as another attack and call it new then I'm not impressed, and frankly there are plenty of attacks in the games already.
No Gyms/League? Definitely not ruling it out, but I think those give a good interim challenge every so often and an end Pokemon League provides a good goal the whole way.
Elaborate Storyline- I'd say this is the most important thing about a hack aside from mechanics like balance and placement of catchable pokemon.
Apocalyptic Themes- I can take it or leave it. The story needs to be good. It can be about anything.
Multiple Regions- It can be cool but honestly the only reason it was so awesome in gold and silver was the nostalgia factor. It was so unexpected to bring us back to the original region. In a unique hack, I think it would be better to make a longer story in one region.
Easter Eggs? Of course! I love cool hidden things in any game.
Twist Endings are just one narrative trick to making a story engaging, and are welcome when done right.
Myths and Legends? I assume this means Lore, and this is hit or miss. Most of what you see in the way of legends is just about the legendaries, specifically the ones you will be catching later in the game. I am more for adding lore about how the universe works.
Smart Trainers- Definitely. Current-gen pokemon games are way too easy. I miss the challenge of gen 1 and 2.
In-game movies- I definitely respect anyone's ability to make endearing or moving cutscenes.
Kanto? Like you'd see a hack without these.
Johto? Pretty much the same.
Hoenn? I'd like to see some of the good ones, like Absol.
Sinnoh? Definitely. Not nearly well-represented enough in hacks. I would like to see more, there are some excellent pokemon in this generation.
Unova? Even more so. This gen has the best pokemon since Johto, and I would love to see them present in hacks.
Custom tiles? If you can do them well, sure. But if you can't, stick with already made ones. There's 5 gen's worth to choose from, for god's sake.
Games that feel like real ones-If you can do it well, sure. Rijon Adventures and Flora Sky are great examples of this. Fun to play, even if a bit tired.
In-game Tournaments? Definitely. I always hated how all the tournaments in Game Freak releases were for FAR after the fact and netted you no EXP.
Returning Characters can be cool as long as they aren't screwed up.
Traitor characters- you can do a lot story-wise with these.
Various Terrains? Really? You need to ask about this? How in the world could you make a pokemon game with just forest or grassy areas?
Other:
My biggest peeve is lack of variety in raisable pokemon early on. Rijon Adventures in particular I think does a great job at providing many different types early on: Growlithe, Geodude, Cubone, Psyduck and many other types excluding electric. He even has a eevee early on, which makes way more sense than getting it in the 6th town when your party is lvl 30 but the eevee is only lvl 5.
Also, fixing evolutions is very important. I.e., changing Graveler and Kadabra to evolving by some means other than trading, and all similar instances, to make it doable on a hack. Honestly, I though leveling up by trading was always a stupid mechanic anyway.
-In addition to this, I would include changing a few late evolutions, for example, the "Deino" evolution track (the sweet new Dark/Dragon pokemon in Black/White) evolves to form #2 at level 54-ish and #3 at level 65-ish. That is way too late, honestly. By the time this pokemon is where you want it to be, you are almost done with the game. That's no fun.
Editing Stats is also a good idea. Not too much, but enough to make some of the pokemon not suck so bad. I like Flareon; it's a great design. But I'd be limiting myself to use it over a just plain superior fire pokemon like Arcanine. The early pokemon games had a bad habit of some pokemon looking neat but having god-awful stats. One of the best things about Black/White is how this is severely reduced. Most of the pokemon are equally usable. I think this is preferrable. Obviously a delicate touch would be needed for something like this.
-Also, you could make a few changes that make sense. For instance, Deino has a high Att but meh SpAtt. However, it's evolutions have very meh Att but insane SpAtt. It's obvious that SpAtt is this evolution line's main stat, so why is the unevolved pokemon so different? Doesn't really make sense and feels out of place.