The easiest way is probably through a .NET web application, although there are libraries for numerous other languages including PHP.
For example, if you had a form with field 'query' submit to this page:
<%
// Get user's query
string query = Request.Form["query"]; // or Request.QueryString for data from the querystring
// Connect to the database
string connString = "your connection string";
System.Data.SqlClient.SqlConnection conn = new System.Data.SqlClient.SqlConnection(connString);
System.Data.SqlClient.SqlCommand command = new System.Data.SqlClient.SqlCommand(query, conn);
// Read your data however you like
System.Data.SqlClient.SqlDataReader reader = command.ExecuteReader();
while (reader.Read()) {
// Deal with your data here
Response.Write(reader.GetString(0));
}
%>
The simplest way to output the data would be using Response.Write(), but you can also use more sophisticated controls. It seems like you just need to output raw results, so Response.Write() may work best.
Of course, the more data you are sending, the longer it will take. However, using a web service shouldn't be slower than any other solution.