How to compare two objects for percentage of equivalence
One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure.

In particular, let $M$ be the $m \times n$ ratings matrix, where $M_{ij}$ is the rating that user $i$ has provided to user $j$.  Look for a $m\times r$ matrix $U$ and a $r \times n$ matrix $V$ such that $M$ is well-approximated by $UV$ (e.g., $||M-UV||$ is minimized, except that missing entries of $M$ are ignored).

Once you've done this, each user can be mapped to a $r$-dimensional vector that summarizes their scores.  Store the set of all of these vectors in a data structure that supports nearest neighbor search, e.g., a k-d tree.  If you have chosen $r$ small enough (e.g., 10 or so), then nearest neighbor search should be very efficient.  This will let you find the users who are most similar to a given user, and thus make a recommendation (e.g., using the  k-nearest neighbors classifier).

There are many other approaches you could use: read the extensive literature on recommender systems and collaborative filtering.

As far as your other issue:


  I have to load in all the users, every time I need to find a set of matching users for just 1 user


Keep the data structure in memory, rather than re-loading it into memory each time.