Improving search performance in large data sets

[cdtotns]

On a WPF application already in production, users have a window where they choose a client. It shows a list with all the clients and a TextBox where they can search for a client.As the client base increased, this turns out to be exceptionally slow. Around 1 minute for a operation that happens around 100 times each day. Currently MSSQL management studio says the query \[code\]select id, name, birth_date from client\[/code\] takes 41 seconds to execute (around 130000 rows).Is there any suggestions on how to improve this time? Indexes, ORMs or direct sql queries on code? Currently I'm using framework 3.5 and LinqToSql