Ordem Usando um parâmetro para o nome da coluna

Você deve ser capaz de fazer algo assim:

SELECT *
FROM
    TableName
WHERE
    (Forename LIKE '%' + @SearchValue + '%') OR
    (Surname LIKE '%' + @SearchValue + '%') OR
    (@SearchValue = 'ALL')
ORDER BY 
    CASE @OrderByColumn
    WHEN 1 THEN Forename
    WHEN 2 THEN Surname
    END;

Atribua 1 a @OrderByColumn para classificar em Forename .
Atribua 2 para classificar por Surname .
Etc... você pode expandir este esquema para um número arbitrário de colunas.

Mas tenha cuidado com o desempenho. Esses tipos de construções podem interferir na capacidade do otimizador de consulta de encontrar um plano de execução ideal. Por exemplo, mesmo se Forename é coberto pelo índice, a consulta ainda pode exigir a classificação completa em vez de apenas percorrer o índice em ordem.

Se for esse o caso, e você não puder conviver com as implicações de desempenho, pode ser necessário ter uma versão separada da consulta para cada ordem de classificação possível, complicando consideravelmente as coisas do lado do cliente.