Rooting. It's easy to do but does come with the risk of borking your phone. the risk is minimal but it's there nonetheless (I like the word nonetheless).
Quite a few of us Magic owners on this very forum are rooted and running a variety of rom's, most notably Cyanogen's. His 4.0.4 is quite a bit faster that the standard 1.5 Cupcake phone and is very nice and stable. Some of us are currently running his latest rom, 4.1.11.1 but if you do root your phone I'd recommend going for 4.0.4 for a while and maybe then go for 4.1.11.1, or wait till the mythical 4.2 which is meant to be the next stable version. 4.1.11.1, though fast, does have a few quirks and being based on 1.6 Donut, some app's are a little problematic.
Apps. There are a tonne of apps out there.
Shopsavvy - a barcode scanner that compare prices
Twidroid - arguably the best Twitter app for Android but the new version today seems a little buggy
Google Sky Map - Just get it and be prepared to go WOW
Weatherbug - a good weather app that can put a widget on your homescreen showing whats happening outside your window, in case you don't fancy looking outside your window.
Handcent SMS - a great sms app that gives you chat bubble style conco's for your sms's
MyTracks - a great program that lets you track, on google maps, your walking/running/biking allowing you to compare times from previous efforts. It's a great app.
and so on.