Best way to search for a lot of users for a web app

What is the best way to search for a lot of users in an application?  Currently we have all the users in a drop down list and well yea... it is really slow.  We have Telerik Controls and try to do MatchFirst on the drop down list, but it freezes.  There are other search options on the same page so if you search by a department it will then just show the users in that department and then it is okay.  Just trying to find a better way to search for a lot of users when they want to do it by username OR First Name/Last name.
In the context we are talking about 25k users
Thanks.