Linux, fdisk: change order of partitions

Recent versions of fdisk start the first partition at sector 2048 by default. If you're seeing some other behavior, then either you're using a rather elderly version of fdisk or there's a bug in the version of fdisk that you're using.

You could also use parted or GParted for this task. They both work with MBR disks as well as with GPT disks, so using one of these tools does not necessitate switching to GPT. That said, GPT does have certain advantages, even on smaller disks. They're minor, but you might want to consider using GPT to get these advantages. (These include having CRCs of important data structures to spot problems, having a backup of important data structures to help recovery from some types of problems, having partition labels, eliminating the awkward primary/extended/logical quagmire, and of course supporting over-2TiB disks.)

Yes, it's possible. My FixParts program will do the job, with some caveats. Most notably, you need at least one unallocated sector immediately preceding each to-be-logical partition. If such a gap doesn't exist, you can shrink the preceding partition by a small amount using GParted before using FixParts. Some Windows tools can also do the job, but I don't know offhand if any of them can handle Linux partitions.

Another option, if you're using a recent computer that supports EFI, is to convert the disk from MBR to GPT form, install Windows in EFI mode, and convert Linux to boot in EFI mode. This is likely to take more effort than the first approach, though. If you care to try it, gdisk can do the MBR-to-GPT conversion.