Android is probably a good place to start. The build tools will run on any OS, there is absolutely no cost to start (even if you want to run code on a hardware device, which will set you back $99/yr for iOS unless this has changed since I last touched iOS development).

You can run and debug your Android apps pretty well on any OS (Linux, Windows or Mac) using the emulator that comes with the Android SDK. Be sure to use the Intel HAXM version of the emulator if you can get away with it (if your cpu supports Intel VT and your Android code doesn't use any exotic ARM NDK stuff) as the ARM emulator is dog slow. I highly recommend having at least one hardware device to test on, though if you can manage to beg, borrow or steal one. You can probably source a year or two old device off craigslist or such for cheap, Android phones generally don't hold value nearly like iPhones do. The emulator is nice for some things but it is generally much more pleasant to run and debug on an actual hardware device.

Java as used in Android has evolved as a language far less than you might expect, but the Android SDK UI framework is quite different than most Java programming because of the way the Android activity stack works, so you'll be spending a lot of time learning about Android Activities, Fragments, Services, Adapters and such. There is a ton of decent documentation/tutorial information online, including Google's own Android docs, plus a plethora of open source Android apps to learn from, so learning it is just a matter of getting in there and getting your hands dirty.