I didn't take my pictures in RAW mode and have a tilted horizon. Don't have Photoshop, only whatever tools came with my Canon 450D, which seem to only work with RAW mode pictures.
How do I do this?
Never seen an imaging software that could not do that, so yes, you can do this.
Adobe Lightroom has a great tool to do that which is interactive. It does cost money, so I would not buy it just for that (there are excellent reasons to do so though).
Google Picasa is free and can do that. Look for the menu item that says 'Straighten'.
It does not matter which file format you used, rotating a digital image slightly is always very destructive to image quality. If you can take the photo again, just to back and be careful. If your camera does not have a digital-level built-in, you can buy a bubble-level that fits in the hot-shoe.
You can use just about any program out there that works with images:
Irfanview can do these transformations with raw and jpg. There are ways to crop without resampling the jpg as well. Resampling is not a good thing for JPG files which are already lossy (meaning that you throw away some of your image data every time you create another version, much like making successive photocopies).
You can also do much more with GIMP.
Canon Digital Photo Professional can crop and rotate JPG as well as RAW. Browse to the jpg file in Digital Photo Professional, right click on it and choose Open in Edit Window, then when that has opened click Tools and then Start Trimming/Angle Adjustment tool. All your cropping and rotating can be done in there. If for some reason it's not letting you, maybe you need to update your version of DPP from the Canon website.