You could use ForgotPasswordAgain's initial "won't work" idea as a subquery to grab the full record for the shortest distances.

select a.* from table_name a 
  join (
    select min(distance) as min_dist, 
           service_id as min_id
           from table_name
           group by service_id
    ) b 
  on (a.distance = min_dist and a.service_id = min_id);
[download]

If (service_id, distance) is not a unique key, this will return all the stop_references with the minimal distance. This may be a Good Thing, depending on the application. If you want only one result, adding the appropriate ORDER BY and LIMIT 1 clauses should do the trick.

/is not a guru
//tried it and it worked for me
[download]