Thank you for the information. The good news is your machine is clean of malware. Let's take each of your concerns in turn.
Step#1 - Java
I normally save this for the end however since you have concerns with Java let's get that resolved now.
WARNING: Java is one of the most exploited program there is. The Department of Homeland Security recommends that computer users disable Java. You can read more about this here.
I would recommend that you completely uninstall Java unless you need it to run an important software. If you need it or are unsure or uncomfortable with removing it then I would recommend that you disable Java in your browsers until you need it and then enable it at that time. (See How to diasble Java in your web browser and How to unplug Java from the browser). If you don't uninstall it, it's also important that you follow the directions below to update to the latest version of Java.
1. Go to this page to download the latest version of Java SE Runtime Environment JRE 7 Update 67.
2. When you click this link you will need to click the "Accept License Agreement" radio button and then click on the "Windows x86 Offline" installer link. You will notice that there is also a Windows x64 link option, however even if you are using a 64-bit operating system, it's very likely you aren't running a 64-bit browser and should only download the "Windows x86 Offline" installer. To determine if you are using a 64-bit browser you can follow these instructions. If you find that you ARE using a 64-bit browser then you can download the "Windows x64" one.

3. Once you click on the appropriate link, please download this to your Desktop like we have with all of our tools.
4. Close any programs you may have running - especially your web browser.
5. Now we need to uninstall all versions of Java that are currently on your machine before we install the newest version. Go to Add/Remove programs (instructions are here) and uninstall the following items: Java 7 Update 65, Java Auto Updater and JavaFX 2.1.1.
6. Reboot your computer once all Java components are removed.
7. Then from your desktop, right click on the file that was downloaded (jre-7u67-windows-i586.exe or jre-7u67-windows-x64.exe) and select Run as an Administrator to install the latest version. Accept all the defaults and you're good to go.
Note: Java has been notorious for installing foistware (software downloaded without the users knowledge). If you follow the instructions I provided no foistware will be installed but that doesn't mean it won't in the future. While performing the install of this software or any software for that matter, pay attention to each screen and ensure you uncheck any extra software that you don't want installed (i.e. Ask Toolbar, Chrome Browser, etc.).
Step#2 - Slow Start Up
1. Let's narrow down your issue. Click your Start button and then type msconfig and hit enter on the keyboard. Answer Yes at the UAC prompt that comes up asking if it's OK.
2. In the System Configuration form that comes up, please click on Diagnostic startup. Click OK and answer Yes to reboot. Is the machine startup better or the same?

Step#3 - Backups
What is the make and model of the external drive you are using for your backups? Your hard drive is about 500 GB in size so you want your external drive to be at least that big. I would suggest double that size, so a 1 TB drive. Please let me know and we'll go from there.
Items for your next post
1. Everything go OK with Java?
2. How is the startup time now?
3. Answer to my Backup question.