AFAIK: Most distros have UID's starting at 500, where Fedora has 1000 since, F15 or F16.
Arch has 100, allthought i thought it was 500 either, i'd change both UID's to 500, in case you're going to test for other distros as well.
Either way, if you dont share /home, for each distro a /home of 1gb suffices, if you have another extra partition with your videos, music, documents (symlinking to the distros /home/$USER dir.
You're line up looks well, i dont recall which grub Arch uses, but i thought it was grub2 too, so you could share /boot.
Adding a user and specify the UID like this:
sudo useradd shanx -u 500
And about which to install first, for me, it worked best when i installed Arch first, but didnt install grub to MBR, but to its first boot partition, while Fedora got installed to mbr.
But thats acutaly more a matter of preference.
Demian explained it quite good, just that it doesnt matter what kind of fs you choose for fedora-root (for instance, you wont be able to access fedora-root-btrfs from arch), the other suggestions are very accurate.