Re:Android
Although Android is pseudo open source, most devices are locked so that you don't have Root access to the operating system.
BTW. Android is basically Linux.
On a lot of devices you can "Root" then, I.e gain full root access, by running various program's that exploit security weaknesses in the OS.
But not all Android devices are Root-able as each manufacturer compiles their own version of Android, so you'd need to do some research before you buy a specific device to see if it easily and safely Root-able
After having said all that... It's not absolutely necessary to Root your Android device to use it with an Arduino.
AFIK. The Mega ADK works with most Android devices, but I feel it's mainly been superseded by other approaches, see below...
A common method to communicate between Arduino and Android is to use Bluetooth in the Android and a Bluetooth to serial module connected to the Arduino.
However, after having been through this in the last 2 weeks, it seems that most cheap android devices don't come with Bluetooth.
Some may, but I can't seem to buy one in any local store here in Australia, and we get a good range of cheap Android devices.
You may however to get a cheap Android device on eBay that has Bluetooth.
So another option I am currently experimenting with is to use the OTG functionality that a lot of Android devices have, where they can become a USB host, and you can attach the Arduino via USB like you can to a PC etc.
I recently bought a $50 tablet for testing etc, and although it didn't have OTG listed in its spec, I found that if I plugged in a $5 OTG cable, that my Android tablet had OTG 
On the Android programming side of things, there is a library for Android dev, that has low level comms for use with Arduino devices etc, which doesn't require the Android to be Rooted
So overall... You can buy a Mega ADK if you want, but there are plenty of other options to communicate with Android.