I linked to the free client. That is what runs on the computer that you you turn on in System Preferences --> Sharing, so you are going to want to install that on the server, not the machine you are connecting from. If you installed it on both it doesn't matter—it was there anyway as part of the OS. It is built into the OS, but a reinstall can fix problems and makes sure you have the latest version. The ARD application is what you would use to connect with from the machine you are sitting in front of. That is what costs money. Apple calling the software "client" can be confusing.
Have you turned on the VNC option under either Screen Sharing or Remote Management. You will need that to connect with a third party VNC app like JollysFastVNC or Tight. If you don't turn that on then the built in Screen Sharing app should just work (accessible from Safari or the Connect to Server dialog in finder by typing
vnc://ipofserver)
It is hard to say if this is a SL bug, or a problem on your network since you only have one machine to test. You could try running Vine Server on your server. You will want to change it's port to something else like 5901, or at least turn off Screen Sharing so it doesn't conflict ports. If you change the port you would connect by typing
vnc://ipofserver:5901
In Vine be sure to use System Server (under Server menu) to keep vine running all the time, even after a reboot.
Vine:
http://www.macupdate.com/info.php/id/11283/vine-server-%26-viewer