Here are some of my favorites at the moment.

Free: DANMAKU death (shmup), Hoplite (puzzle/roguelike), Pixel Dungeon (roguelike), STRIKERS 1945-2 (shmup), Duet (action/puzzle(?)there's a premium version too).

Paid: Super Hexagon (action/brain melting),VVVVVV (platform) R-Type (shmup), Canabalt (infinite runner), Rusted Warfare (rts).

If I remember any other title I'll update the list.

EDIT: If you bought any Android Humble Bundle in the past you should download their app too.

If you can spend 89 cents get "out there".

if you want simple games for a quick fix, i'd suggest "Stick Hero" or "Amazing Thief"...
though the game i normally boot up is "Kritika: Chaos Unleashed".. it's free, but you need a good internet connection for it :)

Bike Race is a quite fun Trials clone that has single & multiplayer. It uses micro-transactions but if you´re not in a hurry you can pretty much get all bikes and tracks without spending anything.

I suggest you download Amazon Appstore as they give a free app/game everyday. Today its Prince of Persia The Shadow and the Flame.
I've managed to make a good library of paid games due to this and the coins promotions.
As for free games on Play store: Gangstar Vegas, Agent Dash, Glow Hockey 2, Air Penguin, My paper plane 2, Diversion, Flip Riders, Paper Zombie, iStunt 2

http://www.amazon.com/b/ref=nav_sap_mas_14_12_24_Dec1_Bundle?ie=UTF8&node=10076151011 if you don't live in america just set the shipping address to somewhere in america, if you ever buy anything it's better to set to a tax free state like Oregon.

You'll only need one game - https://play.google.com/store/apps/details?id=com.blizzard.wtcg.hearthstone

Out of free games first ones that come to mind are Plague inc and Plants vs zombies. My mom enjoys Dots. Heartstone got an android release recently if thats your thing. I'd suggest more, but my tablet is really crappy and relativelly new so i'll update the post when i get home and google a bit.

As for the payed games there are so many of them and many have pc releases as well. There are some Final Fantasy games on android and galaxy on fire comes to mind. You also might want to look at some emulators. I'll try to post more when i can.

EDIT: Ok, here are some more games: Dumb ways to die, Pixel dungeon, Inflation RPG, Jetpack joyride and The impossible game, but thats sadly not free

Few days ago original Kights of the Old Republic appear on google play. I highly reccomend you play this.

Duet

I can reccomend World of Tanks: Blitz and GT Racing 2, Merry Christmas to everyone!

Leo's Fortune, one of the best games ever :) currently on sale (0,99€ Google, 0,79€ Amazon)
https://play.google.com/store/apps/details?id=com.leosfortune

Knights of the Old Republic runs on a Nexus 5 according to reports, so if you haven't played this classic on the PC go ahead and play it on your phone.

1. Install gameboy advance emulator.
2. Install Pokemon FireRed.
3. Catch them all.

My good friend carlest, go check amazon app, you don't even need to do it from your smartphone, there's (or was) lotta games and apps for free, and you can sort them by rating, so it's fun trying to find something you like in 400 pages!!
btw, nice s.p. you have man, nexus5!

.99

gameloft games is running a sale on a lot of their games...modern combat 5, amazing spiderman 2, and need for speed something or other

i also reallly recommend the kingdom rush series...also 99 cents..they're a hero based tower defense game

edit: found this...probably will help you http://www.pocketgamer.co.uk/r/Android/Best+Android+games/feature.asp?c=62850

Geometry dash, Wayward souls, GTA Chinatown Wars, Pewpew 2, King of Fighters-A-2012 (F).

After that Nexus 4 thread, this was to be expected :D

• Dead Trigger (Zombie FPS)
• BADLAND (Ummm... side-scrolling, but you have to try to know what it is)
• Hungry Shark Evo (Eat other marine creatures and humans to keep alive... kinda like Moby Dick, if you've played that)
• Blip Blup (puzzle, but good)
• Shadow fight 2 (1 on 1 combat YOU MUST PLAY THIS)
• Plague Inc. (Strategy)
• Bike Rivals (Trials clone)
• Blek (a new kind of puzzle)
• Walking dead seasons 1/2, assuming you haven't played them on Steam (too lazy to check) (don't even say you don't know about this game)
• Chess Fusion / Chess Free (uh, chess, what else?)
• Any '2048' game you like (1024/2048)
• Daddy long legs (one of a kind, doesn't fit into a genre, try it)
• Dumb ways to die (minigames + infinite gameplay)
• Earn to die (upgrade (is that even a genre?))
• Flappy bird (not on Play Store anymore, ask me if you want the .apk) (flappy bird)
• Frontier Heroes (minigames)
• Hill climb racing (upgrades)
• Into the dead (zombie runner and shooter)
• Piano Tiles (again, you gotta play to know)
• Smash hit (FP-ballShooter)
• Reaper (one of the best RPGs for Android)
• Ridiculous fishing (upgrades + wtf)
• Super stickman golf (1 or 2) (golf. and upgrades)
• Touchgrind BMX (FPbike-racing)
• Vector (parkour)
• Voxel Rush (racing)
• Doodle jump (jumping)

Whew! That was a long list. They're not sorted by which is better (rather, alphabetically, I think), and are a mix of free/paid/IAPs(In-app-purchases).
Edit: Made some of the very good games bold.
Edit2: Added genre/discription in brackets cuz I have way too much free time.

For sure, 天之痕! It's even free with ad support for Android.

Here are my iOS recommendations that might apply to Android if they are available there:
Angry Birds games, Lego HP 1-4 5-7, XCOM: Enemy Unknown, Bioshock, Fruit Ninja+Puss in Boots, Scribblenauts Remix, Contre Jour, Ace Attorney, Worms 2+3, Reckless Getaway, Dungeon Hunter 2, The Cave, Galaxy On Fire 2 (HD), Infinity Blade 1, 2, and 3, THE KING OF FIGHTERS-i 2012, Telltale Games games (Monkey Island, The Wolf Among Us, The Walking Dead Season 1+2, Back to the Future, etc), Aquaria, Sid Meier's Pirates! The World Ends with You: Solo Remix, GTA games, Mass Effect Infiltrator, Kingdom Rush+Frontiers+Origins, Metal Slug games, Ghost Trick: Phantom Detective, 轩辕剑贰 DOS怀旧版, Plants vs Zombies 1+2, Super Hexagon, LIMBO, Asphalt 8, The Bard's Tale, Anomaly: Warzone Earth+2, Romance of the Three Kingdoms (RTK) Plus, Beat Hazard, World of Goo, Batman games, Evertales, Chinese Paladin 1/仙剑奇侠传1 DOS怀旧版, 仙剑奇侠传5 - 剑傲丹枫, 轩辕剑外传 枫之舞 DOS怀旧版, 大富翁 4 Fun Lite, Bastion, Ace Attorney Trilogy, Phoenix Wright: Ace Attorney - Dual Destinies, and Crimson Steam Pirates.

Infectonator has been a lot of fun. It's a strategy game that has you wiping out cities with zombies and consumables like plague barrels and grenades. You can upgrade your zombies, your virus, unlock new zombies & consumables, etc. There's a lot to keep you busy and you never have to spend a cent. You can buy in-game currency with real money but you gain it so fast by moving up to later cities that it's been completely unnecessary in my experience. Overall it's very enjoyable, bite-sized fun.

Mage and Minions is a free ARPG that's kept me playing daily. Granted the video I linked has bad commentary and shows an older version of the game but it'll still do a good job of showing you how things work. All the basics of a good ARPG are there and they're tacking on even more goodness. It has a basic crafting system that they're working on upgrading, a fun gesture system for casting your abilities (draw a V for one skill, O for another, etc), a good choice of minions that will also be able to equip their own gear in a future update, and since they're a small company you get direct access to the devs on their forums. Their freemium system is the biggest reason I plan to stick with them. You can earn gems (their premium currency) endlessly by just playing the game but you don't need to spend very much to get what you want so the game avoids the P2W pitfalls. Gems are mostly about convenience. For example they let you instantly finish training a skill or crafting an item, or you can buy extra skill training slots to allow you to train multiple skills at once. The only gem purchases you really need to make are unlocking extra minion and skill slots but since there are so few of those it won't take long before you're all set.

Level22, Worms, Tank1990HD, Dumb ways to die, DrawRace2, Bomber Friends, Robotic planet, Real racing, Duke Nukem, Carmageddon, Magicka, Minecraft PE, Snake97, Real drift, Max Payne, Bloodstroke, Mass Effect infiltrator, Townsmen, GTA games. Epsxe - PlayStation1 emulator.

Hill climb racing :D

Brave Frontier. been playing it for the past half a year. Addictive and huge playerbase

Free today Prince of Persia® The Shadow and the Flame on Amazon

Get Drastic DS simulator and hundreds of nintendo ds games for free.