Android app: Simon Tatham's Puzzles
This is a collection of logic puzzles I enjoy very much on my Android device. It's an Android port of Simon Tatham's puzzle collection, which normally runs on desktop computers, but it's still very well-suited for touch screen devices.
Permission: Reads logs and writes to USB storage, but requires no network communication. (Nice.)
It's open source (MIT license), too. (Source code on GitHub)