Windows 2000 Professional SP4 ran well if it was a clean install on specs like your system. I almost wonder if you were given it with a troubled OS from the prior owner adding/removing programs with dirty uninstallers as well as the chance that maybe it had some malware on it to lag it out even further.
I still have my Windows 2000 Pro SP4 slipstream that I made, although i haven't used it in years. My push to leave Win2k was that ZoneAlarm Firewall that I had been using with it for years all of a sudden released an update that severed support for Windows 2000, and so you had to be running Windows XP to use their Firewall. But with Windows XP coming with a pretty good firewall, I parted from using Zone Alarm for many years.
As far as Windows Me goes, Microsoft dropped support for updates a long long time ago. Others online have asked for years where they can get the updates to bring Windows Me patched all the way forward to the very last update. I have only seen unofficial sites out there offering updates. * These could be dirty updates with Trojans etc. On an old 80GB Maxtor external drive I think I still have some updates for Windows Me back when I had to support people in the days when most had dial-up and any download was a lengthy process. My employer at the time had DSL and so I'd perform all my security downloads and then burn them to a 650MB CD and then add that to my CD binder that had other tools in there. I may still have updates for Windows 95 all the way to Vista in that binder, and I kept an exact copy of them on my 80GB Maxtor in case a CD got lost etc. That binder is in storage, but I might be able to dig out the 80GB Maxtor and see if I have any Windows Me security update patches available to share if interested. However Windows Me is still a soft target and I would not advise using it for anything important like banking and credit card transactions etc. Also you are very limited in what modern software might actually run on it. Windows 2000 Pro SP4 has better software support, although as I stated earlier you may find that even software you want wont run on Windows 2000 SP4 either as Zone Alarm decided to do with 2000 which ended my use of Windows 2000 since I needed a firewall that I could trust.
I tried using Norton System Works 2003 as a replacement to Zone Alarm, but Norton was a resource hog and slowed everything to a crawl.
If you have 192MB RAM or more Windows 2000 SP4 should run just fine on a Pentium III, however Windows 2000 SP4 on just 128MB RAM causes for lots of paging and so the system slows and you see lots of HDD activity. I have gotten Windows 2000 SP0 to run on just 64MB RAM although it crawls. SP3 and SP4 are resource intensive and you start to see a slow down if you dont have enough memory. If you have patience to wait for programs to load etc, it can run on just 128MB RAM.
Windows Me was slightly less memory intensive than 2000 Pro, and so if your running on a low RAM count this is probably where you see the performance difference if the original 2000 Pro build was clean when given to you.
What do you have for memory in this Pentium III system?