Me puse a buscar y lo que encontre a mano y funcional fue convertir el caracter a ASCII. Tomando de referencia tu ejemplo, quedaría así:
Opción 1:
Código PHP:
SELECT nombre,estilo,bpm,media
FROM historial
WHERE ASCII(SUBSTRING(nombre,1,1) = 241
ORDER BY nombre ASC
ñ = 241
Ñ = 209
Opción 2:
Código PHP:
SELECT nombre,estilo,bpm,media
FROM historial
WHERE ASCII(SUBSTRING(nombre,1,1) = ASCII('ñ')
ORDER BY nombre ASC
Para la segunda opción, sustituirias ASCII('ñ') por la variable que uses en php, ASP o lo que sea. ASCII("$caracter").
Estoy suponiendo que usas MySQL, si es así, te dejo la referencia de las funciones con literales que podrías usar.
13.3 String Functions
En caso de usar otro motor de BD, busca en las funciones propias de la misma.