1] To get into Real DOS mode w/WinME you'll need to boot the system from a floppy. The system recovery disk from a Windows 98 system should work nicely. If you don't have access to this disk send email to wwelch_iii at yahoo.com and I'll email youand image and utility you can use to write a boot disk which should work.
2] Most Linux distributions will boot directly from the CD and include partitioning software as part of the install. Given that your system supports ME it should also support booting directly from CD. Might need to check your BIOS settings to enable it.
3] (Prefered) Buy Partition Magic and use it to re-partition you hard drive. At ~$70, it's not inexpensive, but it's definately worth the money
4] As a response to answer #2, I would definately NOT run fips from a dos window, not if you value the integrity of your harddrive. fips needs to run without interuptions and that can not happen in a multitasking enviroment such as WinME.