So we are creating a new Android App. We'll have a name for it, and a logo, and the specific functionality of the app is something that hasn't been done before (we searched). The app is going to be released as a free app at first. How do we protect ourselves from someone copying things like the logo, the name of the app, and really all of the functionality?
Going even further, how do we protect ourselves from these things across platform as well, such as someone trying to develop a new app that does the same thing on the web, or even on the iPhone/Blackberry.
This is a multifaceted question and so you get a multifaceted answer.
First off, when you wrote the code you automatically had copyright on your code. If you hire someone to create the code the ownership of Intellectual Property should be spelled out in the contract, if not then how ownership is handled will vary from state to state in the US.
Beyond copyright it gets more complicated. For your name, logo, etc you will want a trademark. Technically you can do this on the cheap but it will take months at best, and that is assuming you know exactly what you are doing. Otherwise you will need to hire a trademark lawyer to help you get through that process.
At this point you are safe from someone literally stealing your code or stealing your name/image. If you want to keep someone from recreating your code themselves on another platform and releasing it under a new name, you need a patent and that's about impossible for software. Not impossible, just about. Your software would have to do something truly never seen before, otherwise you'll eventually run into a larger corporation who already has the patent.
I say, start with a strong trademark. Then if you have success, even if someone tries to beat you to another platform you still have the name recognition and will hopefully win out eventually.
Assuming you are in the U.S. (other countires laws may be different: