You seem really new to linux, not knowing about cvs is kinda a phun killer in linux. Anyway, to the point. The links above should provide you enough information to get your Ultima online client working. The second link is just the client and readme. It is very brief but if you know a little about linux you should have no problems getting everything going.
That is something to try.
I havent played Ultima online in linux before, I am just offering information on that which is on the internet.
The other option which I would try would be Wine.
I dont believe you would need winex to run it. I would first uninstall the version on redhat already using "rpm -e wine" in command prompt and "rpm -e Wine" then download this:
and change to the directory and type "rpmbuild --rebuild "thefilename"" and the it will say the files created usually in the /usr/src/RPMS/i386/ directory rpm -ihv "filename" to install the built rpms.
Google is my favorite tool for finding information to correct problems.