So you're using Mesa.
We may not be in 2006, but Mesa is
You want to play Eschalon with decent frame rate ? Just use fglrx.
But it won't be that simple of course.
As you may already know, AMD dropped all cards under R600 with fglrx 9.4, so you will have to use an old kernel and xserver in order to use fglrx 9.3 (the last one that support your hardware).
And yeah, i do not doubt that your radeon card is working fine, but it is a fact that mesa is *not fast* with OpenGL. Yeah, some 3D games works fine, but Eschalon with his 2D Engine is slow.
EDIT: If you don't want to use an older distro, you can try using last mesa/libdrm/xf86-video-ati/kernel and try KMS + Gallium3D.
This is supposed to be faster than classic mesa, but it is still realy young and not realy optimized yet.