One thing I'd avoid at all costs is writing your game directly in Java or Obj-C. While those are the "official" ways to program on Android and iOS, doing so will lock your code to one platform, and you don't want that. (Which is awesomely ironic for Java when you think about it. )
The easiest way would be to use a readily made cross-platform game engine. Since you mentioned having experience in C#, you might be interested in Unity 3D. While I'm personally not a fan of writing games that depend on an proprietary engine I don't have the source code for, doing so will spare you the entire gory engine programming and get you to the meat of the game a lot faster, and Unity is more than good enough for Unity. (It's actually packed with features that 99% of the indies don't even have the means to use.)
If you have simple graphical needs and would like to get your hands dirty, you might also opt to write the game in portable C++ and use Java/Obj-C only to wrap the platform's API. It's a lot harder but it's very rewarding when you see the end of it. I really wish both Apple and Google made C++ a 1st class language like Microsoft, but I guess that helping developers to port their games to the competition is against their best interests.
Then there are middle grounds like MonoGame or OGRE for mobiles. Basically you have the graphic rendering library but not an entire game engine. I dunno how good or stable those libraries are though, I haven't tried them.