This is one of my favorite games I've found so far.
Top Picks for Apps to Help You While Away the Minutes
Shortyz is an open source crossword puzzle application for Android. It supports downloading of free puzzles from around the Internet, and from the New York Times web site if you have a paid Times Select account. It is available in the Android Market via the QR code.
Shortyz has also been featured on the Google Web Toolkit Blog.