A couple of questions for you...
When you say that you can connect slowly from the server (as opposed to quickly from your PC), are you saying that ArcCatalog is installed on the database server? In other words, the connection is very slow when using ArcCatalog on the same server as the database to which you are trying to connect? From your PC, connecting in the same fashion to the same database is fast? Just confirming what I think you're saying.
Also, I noticed that you didn't mention any errors... so you are not receiving any, correct? Once the connection is finally made in ArcCatalog from both your PC and from the server, no tables ever appear in the table of contents? Are you certain that the user account contained within the OLEDB connection file has SELECT permissions to view the data or is assigned to a role that has those permissions? It sounds like the account does have CONNECT and/or RESOURCE, but verify this too please. One last item to check... are any of the roles that are assigned to the user account set to be Default roles or are all of them set to not be Default?