Android to arduino- best board option for wireless
You mentioned the Mega ADK, It is quite good, being specifically designed for Android projects, but it is not wireless. If you need wireless, it could be worth taking a look at the Arduino BT. You would have to do the Android app separately, but once you made that, the BT has built-in bluetooth and useful libraries that make connecting easy. Your other option would be a bluetooth shield, of which there are plenty, though none of them are official. There are also WiFi and NFC shields but they are more complicated. Possibly still worth a look.