I've tried deleting apps, moving to the SD card (sadly this is not so much of an option with most apps), getting rid of my live wallpaper and deleting pictures and videos but the phone is still running SOOO slowly. What can I do? Must I root the phone?

Without root access you are fairly limited with speed increases, my only suggestion would be a factory reset. If that does not work and you believe it should be running better than it is, send the product in if you have a warranty and have them send you a new one. Hope this helps let me know how it goes.

But be careful with rooting your phone without someone who knows what to do. You'll lose your warranty as soon as you root your device.

-----
Mein Google+ I Mein Twitter I Mein Facebook

Yes, I agree do not root unless you have looked into it and are confident in your abilities to do so without bricking your device.

Happened to my Spica. Do a factory reset. All your apps will go but the phone will run fast and you can reinstall them later.