Well, to have it be crisp while at such low resolutions, there's only really one route. Vector graphics. One such suggested filetype is SVG (Scalable Vector Graphics), but it is not enough to just load in a bitmap and then export as SVG, because then you're trying to just force a rasterized file into a vectorized one, it can't look any better than the original by that route.
You're mentioning fonts though, so I guess you're typing in Illustrator and it looks clear. Fonts are natively a vector format, so when you export that as svg, it should remain nice and crisp. Not necessarily quite as much though, fonts often take a little extra cheating for extra crispy crunchiness with subpixel level control, depending on your OS.
Depending on your original file, you may need to essentially trace over and recreate the vectors for your file, and only then export as SVG.
Also Save to/for web is code for "butcher my file with lots of compression to make it small and load fast."
I promise 100% that SVG is the way to go. You already have Adobe Illustrator, but for anyone that doesn't, Inkscape is another vector graphics editor that is free and open source and can easily be used to get sharp logos at any size.
PDFs also use vector graphics (mostly, though you can also embed raster images), but they are not supported for logos on the web (the one shown in tabs, etc...).
There are many tutorials around for creating them, e.g. in Inkscape (so anyone can try) https://www.youtube.com/watch?v=mX7Nbj1xFco Just at the end save as SVG instead.
And also in webpage form: http://lebende-bilder.blogspot.qa/2014/03/tutorial-how-to-create-logo-in-inkscape.html
If you would rather go with PNG still (a raster format) then it is probably best to start with a rather large file and create many scaled down version for use in different parts of your site. The scaling algorithm can also matter, I would suggest using something at least on the level of SincLanczos (it is available in the free and open source GIMP and in Photoshop for sure as well though the naming may be slightly different). A tutorial that goes for a PNG logo in Inkscape is here: http://audioplastic.org/blog/2011/07/03/inkscape-logo/ I think that some of the effects they used are rasterized and that was the motivation for them to use a PNG.
Here is a great tutorial on the topic using Illustrator: https://design.tutsplus.com/tutorials/svg-files-from-illustrator-to-the-web--vector-20899
As he points out, some of the things he is doing are not needed for text, but if you're starting from a raster image, then you somehow need to get from that to vectors. Inkscape has a tool that attempts this automatically, but it can only really handle simple inputs well. I'm not familiar enough with Illustrator to say if their tool (if they have one) is any better. That is why I suggested earlier that you may need to trace the vectors over the raster image to recreate the logo and then ditch the raster image and export.
SVG will prevent the wildly different versions as the OP noted at the start, because the logo will be represented as mathematical equations once in SVG (it does not embed fonts, they are converted to the equations for the shown shapes). In PDF you actually could get wildly different font display, especially if the embedded font isn't supported by your OS, in which case it will use some other default font to display the text.
I will reiterate once more, DO NOT use the web formats for anything you want shown in high quality. The purpose of that export is to save bandwidth and decrease load times by using lots of lossy compression (while hopefully keeping the image barely acceptable) because sites don't want to waste that bandwidth. That said, it has its uses, not everyone is looking to display everything at absolute maximal quality. SVG also keeps sizes down though, but many things we want to show don't work as SVGs, e.g. photos we take with our cameras are rasterized from the instant we take them and it makes little sense to shoehorn them into an SVG. Depending on if that is the central focus of your site or not, you may or may not want to compress them for web (e.g. you probably don't want to for Flicker's user images, those images are sort of the whole point of it, but you may want to for images in forum posts like this one.