When I was building a linux PC in the late 90's, I bought a Matrox Millenium with the memory expansion to 8MB which could do 1600x1200 with 24 bit color.
That was an awesome card for the time, and an incredibly stable analog signal, which Matrox was known for - other cards at the time would get fuzzy, shimmer, or have ringing / ghosting.
At the time, for good support you needed to *buy* an X11 server for accelerated graphics support. I forget which one I paid money for, but within a few years it wasn't necessary as open source had caught up.