You'd need the JRE, but not the JDK. The JRE is used for running Java programs (and many / most PCs will have it installed anyway because you need it to run Java applets or any other software written in Java.) You just need the JDK if you're doing Java development.
Are there any programs that would change an Executable Jar File to an .EXE, or similar, format?
Not really - it doesn't work like that. Most of the programs you find out there that wrap jars up in exes will literally be doing that, the exe will just contain the jar and launch Java to run it. So you'd still need Java on your system for it to work. The one advantage these do have is that if you haven't got a JRE installed, the exe can often prompt you to download it (whereas a jar file just wouldn't work.)
Other than those type of "wrapper" programs, the others generally come in two sorts, those that wrap up the jar as well as a JRE in the exe file (creating a huge file and meaning really you might as well just download the JRE and install it separately) or those that compile the Java code to machine code rather than Java bytecode (GNU GCJ is the only one I know that does this and not really practical to use in this case, it'd be a lot of work assuming it did work!)
In short, there are various programs around but they're not a magic bullet and the vast majority of the time you're better off without them!