Tetris is now availble from EA Mobile in the Android Market. Not sure if it's worth the 5 bucks. Check out a review. EA Mobile Tetris Review
Classic tetris is free in the market and is a perfect interpretation of the original game. Did I mention it was free. I had the EA version on my iPod and it is easy and boring.