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
/data directories for the app.
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
/system partition would be unaffected. If the app were to stick a payload on
/system then the only way you could really be sure you're clean is if you completely wiped all of the internal memory of the device and then reinstalled a new ROM, I would say. Even worse would be if it somehow managed to write a malicious bootloader or something of that nature, since in some circumstances it's possible to write to the bootloader partition from userspace (given proper permissions).