Abduction! - Addictive and cute;
Cestos - slightly random, but addictive network multiplayer with chat;
Simon Tatham's Puzzles - all the classics with simple but nice UI;
Tilt-mazes, nice puzzle, but now stuck.
I'm really waiting for the next wave of JNI enabled emulators, Android Arcade is not perfect yet but it's getting close.