General Requirements
Minimum OS version: Android 2.1
Processor: Recommended 1Ghz. Minimum 550Mhz (Droid 1).
Memory: Must support VM Heap Size of 24M or greater. (Some older phones are only 16M and fail during map load, returning an OutOfMemoryError!)
Screen Size: The game runs natively on WVGA (800x480) or FWVGA (854x480) screens. Other screen sizes are handled via scaling (see below).

QVGA (240x320): Scaling
WQVGA400 (240x400): Scaling
WQVGA432 (240x432): Scaling
HVGA (320x480): Scaling
WVGA800 (480x800): Native
WVGA854 (480x854): Native


Tested/Reported working phones:
Motorola Droid
Motorola Droid X
Motorola Droid 2
HTC EVO
Samsung Galaxy S / Captivate / Fascinate / Vibrant / Epic 4G
HTC Desire
Nexus One
LG Ally


Untested phones that probably work:
(These phones need verification. If you have one of these, please reply to this thread and tell us how it works!)
Droid Incredible by HTC
G2
MyTouch 4G


Untested phones that may work using resolution scaling:
(These phones need verification. If you have one of these, please reply to this thread and tell us how it works!)
(Also, some of these phones have slower processors which may not run the game at good framerates.)
HTC Magic / myTouch 3G (HVGA)
HTC Tattoo (QVGA)
Motorola Cliq (HVGA)
Samsung Moment / Samsung Intercept (WQVGA)
HTC Wildfire (QVGA)
Other QVGA, WQVGA, and HVGA phones.


Phones that definitely will not run the game:
Vodafone 845
HTC Hero / Droid Eris - reportedly works rooted though
Old phones running android 2.0 or below


Keep in mind that while the "working" phones listed above may run the game, they may not necessarily run it at playable framerates if they do not meet the CPU requirements.