If I downloaded a non-market application and installed it and discovered it may be malicious, does removing it from the list of applications completely discard it and help mitigate any security issues? If not, does resetting the phone back to its factory settings mitigate any security issues?
I don't know that there's a definite way to answer this. It would be almost entirely dependent on how exactly the app was attempting to infect your phone and how successful its attempts were.
In the simplest case, maybe the app is sniffing data or something of that sort. For that case, uninstalling would basically remove the threat since the app would be gone. Nothing is left behind when you uninstall, including the
Slightly more complex would be an app that put a malicious payload somewhere on your system's publicly writeable storage. In that case removing the app would not necessarily be enough, depending on what exactly the payload did and how it was designed. Uninstalling could potentially cause the malicious code to become inert on reboot since the app may need to fire up a service on boot, but that's hard to say. Formatting your SD card and doing a factory reset would probably clean it up in its entirety.
The most nefarious case would be an app that gained elevated privileges on your device, either through an exploit or effective social engineering in which you grant access yourself. In that case a factory reset would not necessarily be enough, since the entirety of the