Welcome to linux!
Partitioning is just like picking a linux distro, you'll find out over time what works best for you. Typically I install everything to a single partition and use a separate FAT32 partition to store important files (so my wife can access them from XP).
I have a separate boot partition that uses a 3rd party bootloader to allow me to select windows or linux. You can use the Grub bootloader, which will come with Ubuntu to do the same thing (Saikee, who you'll see around these forums has a page on the net with 100+ distros all booting using grub, so it's more than capable). If you use Grub, I would recommend making a separate /boot partition of 100MB or so. Then if you delete Ubuntu later, you will still have your config files to boot up windows (otherwise, you have to do some command line stuff to restore the windows bootloader, etc, etc).
As for partition size, a typical linux install takes up about 5GB if you install everything, including the kitchen sink. If you go for a minimal install on Ubuntu and then only load the things you want, you'll probably be more like 1.5 GB. So in general, I would say 10GB is more than plenty for most systems. If you're doing video or MP3 stuff, you might like more space.
You shouldn't need partition magic as each install CD has partitioning tools. The only reason you might need SystemRescueCD for partitioning is if you have to resize an NTFS partition as not all distros have that option. Smart boot manager is a good piece of software to use if you don't want your linux install to touch Windows at all. What you would do is install grub to the root partition (not the Master Boot Record) and then chainload it with SMB from floppy. So if you boot without the floppy, then it boots windows directly. If you boot with SMB floppy, you can pick which to boot.
Anyway, that's my
. There's lots of information on dual booting around these forums and on the web. If you have problems with the setup, be sure to post back here before doing anything rash like reformatting the whole drive. If this is your only machine, you might keep a Knoppix CD handy so you can get back online if you hose something up. Then people here can help you fix it...