I too looked into Hadjieleftheriou's Spatial Index Library before settling on shapelib's quad tree (for Quadtree). My C++ chops are a bit flabby these days, and Frank's C code is very easy to work with. Given my limited time and minimal requirements, the choice was obvious. Now, I'll definitely be looking into the QGIS R-tree implementation.
Jason Birch points out new MapGuide Open Source demos that beg to be compared against the ArcGIS Server ADF demos. I spent a few minutes trying out the three generic tasks and must say, this is more like it. Autodesk is employing some UI and graphic designers. They haven't found the sweet spots yet, but are closer than the ADF team. They need to drastically reduce the number of mouse clicks needed to theme a layer -- the color picker is particularly painful to use. The markup task is poorly named (HTML is markup), and almost useless. The larger goal is to share placemarks (or lines, or polygons) with other users across applications. Why jail them inside MapGuide? The feature query task ought to support more complex multi-property queries, and the polygon digitization tool is a nightmare (The ADF's performs much better).
It's an improvement over the abysmal ArcIMS client, for sure, but is less impressive than all the hype suggested. The HTML table of operation panes looks and feels clunky. Reordering the panes conflicts with Firefox's right-click menu. The scale bar is nowhere near as sexy as Tim Schaub's (in PrimaGIS and OpenLayers), and the scale slider is nowhere near as smooth as the one in Google Maps. I was expecting it to feel more usable and look more appealing.
There is a request in comments for more details and examples of declarative programming with MapServer. Before I elaborate, I must stress that I'm advocating a new-ish, different way of looking at MapServer. It's not widely recognized that the instructions encoded in a MapServer mapfile comprise a domain-specific language. (Norman Vine, for one, gets it.) The reference itself is concerned only with the content of a configuration file, and doesn't acknowledge the existence of a language. Like it or not (and I do have my issues with the syntax and semantics of it), there is a map language. To embrace the map language is to benefit from simplicity, usability, and portability. Now, don't misunderstand, there's nothing inherently wrong with imperative programming. The problem is that imperative mapscripting exposes its practitioners to the many rough edges and pitfalls of MapServer's internal API, and produces less than portable applications.