I am not a lawyer and this is not legal advice.
The likenesses of fictional characters are copyrightable works (not trademarks), and the examples you gave are most certainly copyrighted.
Can I use those images in the first place? What are the implications?
If you negotiate a license with the copyright holders, certainly. Otherwise, US copyright law provides an exemption for fair use, allowing portions of copyrighted works to be incorporated into original works for demonstrative or educational purposes. There's also an exemption for parodies under Campbell v. Acuff-Rose Music, Inc. Without knowing more about your app, it's hard to say if you'd be covered under an exemption, and the decision is ultimately up to a court if and when an infringement suit is filed against you.
I know that I can't use a full batman drawing from an artist, but how about the batman symbol (which is universally known and used everywhere). Is there a difference?
Probably not. The popularity and wide use of a work does not affect its copyright status.
And finally, If I do get a C&D order, can I simply remove the content and avoid any further legal implications?
It depends on the wording of the cease and desist order. If it explicitly says that they will waive their legal right to pursue a claim against you if you comply, then yes, you'll be safe. But in all likelihood it will simply be a threat to sue if you don't comply, and complying does not necessarily mean that you're safe.
Also note that a cease and desist does not necessarily mean that what you did was illegal; see chilling effect. It just means that the copyright holder believes your use is an infringement.
