Within my own experience, Seagate is reliable and performs well. I've had a few that were defective on delivery, but my dealer quickly replaced them and none has gone bad or developed bad sectors in use. Samsung has a mixed reputation, and I've known a few that developed bad sectors within a short time. I've never used Maxtors but they have a bad reputation.
As rohanbee said, SATA is only slightly more expensive than PATA, but performance is also only marginally better. You have to check first to see if your motherboard supports SATA. Also, Win98 and ME do not support SATA as the boot drive.
As to moving your data, there are ways of backing up, creating images and so on. But personally I connect the two HDDs and just copy everything on to the new drive. Copying with WinXP is much faster than with Win 9X or ME.