This is a good list, I'd definitely put Danganronpa: Trigger Happy Havoc on that list aswell, one of my favorite games this year.

LBP and Uncharted are very fun. MGS HD if you haven´t played before. Star Ocean First Departure is a good 5 dollars psp game that you can get on vita digital store.
Persona 4 Golden is not bad, but not as cool as playing on the PS2, or even Persona 3 on the PS2, which were much more scary and were a perfect fit for the big tv screen.

Gravity Rush was a big disapointment for me, because it is made by SCE Project Siren, which is the old Team Silent from Konami, developers of Silent Hill and Siren Blood Curse, my two favorite games. Gravity Rush is nowhere near as good as these titles.

There are a bunch of free PSN Plus games, so I recomend to you this: get on sony online store and get all the free games you can, even before your Vita arrives.

I can't really recommend that one. It is fun at first but the more people you get the more the framerate drops and the boss battles are extremely frustrating like that.

Senran Kagura Shinovi Versus is a must have import :^)

I don´t get this obsession you kids have with framerate, back in the day all we had were slowdowns. that was how it was and we liked!

http://www.youtube.com/watch?v=BbU4Cb4A4-o

Define hidden gems.

And do you speak japanese ?

I know that you weren´t serious, but stable 30 fps really isn´t too much to ask for in 2014.

...especially for a game with rather poor visuals like New Little Kings Story.

Velocity Ultra and Lone Survivor. The latter is on PS+ starting today, so no excuses!

Stuff I haven't seen mentioned yet - Terraria is a great port and fun game to have on Vita. Atelier Totori Plus is great if you like slower-paced JRPG's. Earth Defence Force 2017 is something you'll either love of hate (I'd recommend watching some videos of it), but if you do like it then it'll hook you in for days. Zombie Tycoon 2 is a throwaway RTS, but one you can have a lot of fun with while it lasts.

Also, although they're a lot more well known, I can't recommend these 5 games enough: Tearaway; Dangan Ronpa; WipEout 2048; Gravity Rush; LittleBigPlanet. All of them felt like perfect handheld experiences to me.

And on a final note, some games I cannot recommend at all - A-Men is rubbish, I really wanted to like it because I like Bloober Team but I just couldn't; Super Monkey Ball Banana Splitz is a really cheaply made game filled with content, most of which isn't fun; Dynasty Warriors Next is fun until you get the millionth forced touch screen battle forced on you, try waiting for 8XL instead if you're interested.

Honestly, I agree with you that the game is poorly optimized and ran extremely badly in two particular places (in the town & during the Dragon boss battle), but regardless I'd still recommend the game.  I really had a fun time with it and the framerate problems didn't hold that back.