App storage help needed on HTC Desire... how does APP2SD work, and what rom should I reflash with? Help this noob please...

I have an HTC Desire, and I'm inmensely happy with it. I only have one problem: I'm constantly out of internal storage space for my apps, so I end up having to uninstall apps that I like, and I still struggle to have more than 15mb left.

Right now, I only have those apps that I REALLY like/need, and still I'm at 15,69mb free, which seems very weird to me.

First of all, this is what I've done to my phone:

Soon after I received it, I upgraded to Froyo. I used this rom, but that was before the official HTC 2.10 release, so I would be interested in upgrading since I'm carrying the 2.09 version.

The process I used was:

· Root with unrevoked

· Titanium backup

· Nandroid backup

· Flash radio

· Flash OS

...and that was it.

Now, for my actual noob questions:

1. [SOLVED] I've heard that people sometimes also do a "wipe" before they flash a new rom, but I didn't know what it was at the time... could it be that, since I didn't wipe the internal memory, there's duplicate stuff taking up space there?

2. [SOLVED] How do I use the APP2SD thingy? Right now I think I'm using the Froyo one, which consists on browsing through the app list and trying to tap that lame "Move to SD" button if it's not greyed out (which it is 70% of the time, since most apps don't seem to qualify for card storage). I've read something about creating an EXT3 partition, which I know how to do, but then what?

3. After some months, I've discovered wonderful stuff like LauncherPro, Extended Controls, etc., so I've replaced HTC Sense with them and thus wouldn't mind installing a non-HTC rom. But at the same time, stability is really important to me, so I don't like to install experimental/unstable roms in my phone. I don't like having to flash my phone very often because I travel from time to time and it could leave me hanging if the phone suddenly stops working.

So... what rom would you recommend to me that has support for APP2SD and is stable (as I said, I'm fine with the one I used, it's just that I don't mind trying something new). One thing I'd like to mantain are the stock animated wallpapers... I don't know if they come included with all the roms or not.

4. [SOLVED] Also, what would be the best steps to follow to flash that rom now that I know about the wiping?:

· Titanium backup

· Nandroid backup

· Wipe (how do I do this?)

· Flash new radio

· Flash new OS

· Restore Titanium backup

· ...

· Profit!?

5. [SOLVED] Do I need to clean any of the data inside the SD card as well? After all, many apps have been moved there... Should I just save all the media and just format the card, or do I need to take something else into account?

6. [SOLVED] What happens to the paid apps I installed? If I restore them with Titanium backup, will they be up and running again? If not, are they tied to my Google account and thus will be available to download for free once I login?

Thanks in advance for any replies, these are just all the little doubts that I can't quite seem to solve just by googling. Excuse me if some of them were too obvious.

---

Edit: Thanks a lot! That got most of my doubts solved, and I've edited my post accordingly. There's still one doubt I have:

I see you guys recommend 2 different roms: LeeDroid, which apparently includes HTC Sense, and Cyanogenmod, which as far as I know, doesn't.

Now, could anyone elaborate on the differences between them? What kind of things will I miss exactly if I install a non-HTC rom? Is it only the launcher ("+", "Phone" and ^ buttons) and the HTC widgets? Or is there something else? For example, will the facebook/contact list integration still be there in CM? Will the animated wallpapers be there as well in CM?

I did replace HTC Sense launcher with LauncherPro, but I don't know if there's more to HTC Sense than the launcher.