My favorite new game to play on my Fire is "Safe Trip or Not"
Its currently only on Google Play store but I was able to successfully sideload the APK from my Droid Razr to my Fire.
Its the classic French card game "Mille Bornes"
http://en.wikipedia.org/wiki/Mille_Bornes
just not the officially licensed but their own version of it. But it plays exactly the same. You can play with another person or with multiple CPU opponents at different difficulty levels.
Lots of strategy and changes every time and never gets boring
If you have access to the Android Market/Google Play store you can get it here:
https://play.google.com/store/apps/d...=search_result