b_rros, Congrats! You picked the right PC to begin with! I suggest starting with some Monkey Island and perhaps a couple or two other great DOS titles. I don't know for sure, but Quake II might be playable in software mode. Your S3 videocard is fine, it's fast and compatible, although 2D-only.
The best upgrade at current state is getting a Voodoo Graphics or a Voodoo II card. That will introduce your PC to a whole new world of Glide games. Grim Fandango is great on a Voodoo card, Quake II is really shining. If you wish to upgrade your CPU, you should first make sure your motherboard supports it. I would suggest going straight to 233MMX if you have 3D in mind - some extra beef is never bad for it. However, if you like DOS titles better, your CPU is just fine.
Considering Matrox Mystique 220, I own one and I can say that it is an excellent card. It has a great 2D core and some 3D capabilities I find curious. If you can find one for cheap, go for it! I love playing Tomb Raider on Mystique, it does not have much alpha blending the card can not perform, and looks very crisp and retro compared to the smooth Glide version. There are other games for Mystique, I'll find a full list if you're interested.
And I don't want to disappoint you, but forget about playing Half Life on this rig. Especially in software mode.
btw, here's one of my old builds that started as Pentium-100 with FX chip set, 16MB of RAM and S3Trio64V+: My Pentium MMX gaming rig
And here's the website that has a lot of good info on CPUs, chip sets and other stuff of the era, it helped me a lot: http://www.pcguide.com/
Good luck and have fun!