As a reference point: my 7800GTX 256mb card tops out at 72C, so if you can get an X1900 card to stay around 70C, you're doing well. I hear that you can expect up to almost 90C without much worry. Though some may disagree, I think that anything around 90C or less is okay, but any higher and you might want to think about 3rd-party coolers or a better case.
I'm looking to buy an X1900 very soon, and the research I've done on the X1900 seems to indicate that you can expect temps at load over 80C, though with the right tweaks (ATiTools, for example) you can lower the temps down to around 70C. The main issue is the fan control: apparently, the default settings make the card run a tad hotter.
I read a very positive review on the Acclero X1 and X2 coolers. The cards come pre-applied with thermal paste, so there's no application involved -- though you will probably have to remove the old compound. It runs very cool, around 10C cooler, but the fan does blow the air back into the case. That said, this doesn't seem to impede its performance. My guess is that you will need some good air circulation to dissipate the heat a bit, which means that those with cramped cases might want to reconsider. The rest of the installation involves securing the cooler to the card via incluced screws and washers.
The big selling point of the Acclero coolers: they're whisper quiet, around 2000 rpms. Just remember that removing your stock cooler generally voids the warranty (some will still honor it, however), so you might want to wait a few months after purchase to make sure that the card isn't defective in the first place.