They both (Ubuntu and Fedora) come with a Gnome desktop by default, for both you can install any other desktop if you like, for both you need extra libraries/codecs for the basic multimedia engine (usually gstreamer or xine, Ubuntu uses gstreamer, not sure about Fedora today) to be able to play everything you can find (in Ubuntu you can install a meta package or a couple of library packages to get the codecs, or just play the file in Totem which leads to apt trying to find and install the needed codec automatically) -- in short, the software side in both of them is about the same. It's just what comes in the box and what you download after the setup yourself (using a package manager), and what's under the hood. I myself prefer Debian-ish distributions over Fedora-ish, but in the end it's not a big deal.
If you used the DVD for Fedora, I wonder what all you had to install from the web that wasn't on the disc if it was such a big thing? I mean, the DVD includes tons of software..so probably if it didn't have what you wanted, probably no distribution has
Ubuntu has a selection of software that comes with the installation, a lot less than Fedora with default selections I guess, but that's the beauty of it -- there's not so much to remove/switch if you aren't ok with them. And in my opinion the programs that come along the installation do fit into the system, whereas with Fedora it has always been (for me) a huge consumption of time going trough the package selections before or after the setup to get it fit for me.
Whatever one Linux distribution can do, the others can as well -- so don't be afraid of missing something by switching a distribution. If you feel OK with one distribution, don't switch; the others can't offer anything you couldn't get by modifying your current distribution, and most of the time you're not satisfied with the standard installations anyway, so you'll do some modifications anyway. Nowadays the top things on distribution selections seem to be ease of use, good looks right out of the box and easy package management. Both Fedora and Ubuntu do deliver these (maybe apart from good looks, if you dislike them), so neither one is a match winner.
EDIT: Well it seems I only talked about Fedora and Ubuntu..but it is the same for all (at least unspecialized) distributions; the differences are in personal taste, not what they can do.