If you want to do phone-arduino interaction, this is probably your best bet:
There's also this which is essentially a direct competitor but isn't arduino:
https://www.sparkfun.com/products/10748?
You can also try to connect via bluetooth. There was (is there still?) an arduino Bluetooth, and I think I've heard of people getting a USB host shield and plugging a USB bluetooth adapter into it. There may be other ways, too.
I haven't tried any of these options since I don't have an android phone. But hopefully those links will get you started.
(also, paragraphs are nice)