Well, you could easily try both
Not sure if there's a live-cd version of Fedora 9 out yet, but when it comes, get Ubuntu Desktop disc and Fedora live-cd, try them both and see which one you like more. You can configure the user interface to be identical if you want (both ship with Gnome desktop, or KDE as alternative) so that can't be the thing you're pondering. I'd say pay attention to the configuration utilities (note: both give just as much power to the user, you just need to know where to get it -- what tools to use, what files to configure) and package management, plus community of course.
I would vote for Ubuntu because of it using Debian's apt for package management, but it's just my personal liking, not a solid nature constant or anything. And as far as I know, you can disable SElinux in Fedora, so that's not a problem there..
Why I would personally pick Ubuntu and not Fedora is because of apt, because Ubuntu makes multimedia codec obtaining easier, because Ubuntu needs only one cd to install a perfectly fine desktop (of course both allow for customization after setup, but why would you want to download and burn several discs instead of just one?) and because I just feel like it. Each and every one of those things can be turned to I'd-prefer-Fedora if you're a Fedora fan, so just try them out
better use something you know than something you hope you learn to like, unless it's a hobby or you have tremendously much spare time for tweaking.