Clasificación basada en registros anteriores y siguientes en SQL

Puedes hacer algo como esto.

1. Identifique la primera y última letra de cada padre usando ROW_NUMBER() y PARTITION BY
2. Hacer coincidir el último registro del id anterior con el primer registro del siguiente id .
3. Compruebe si la identificación del segundo padre tiene alguna letra que coincida con la letra seleccionada arriba
4. Use un LEFT JOIN y usa CASE o ISNULL para establecer una prioridad más alta para dicho id registro en el que la letra había coincidido

Consulta

;WITH CTE AS 
(
SELECT id,ParentID,letter,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID) first_element,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID DESC) Last_element
FROM Child
), CTE2 AS 
(
SELECT c1.id,c1.parentid,c1.letter,c2.parentid as c2parentid
FROM CTE c1
INNER JOIN CTE c2
ON c1.last_element = 1
AND c2.first_element = 1
AND c1.id +1 = c2.id
), CTE3 AS 
(
SELECT C.parentid,C.id
FROM CTE2
INNER JOIN child C ON CTE2.c2parentid = C.parentid
AND C.letter = CTE2.letter
)
SELECT P.number, C.letter
FROM Child C
JOIN Parent P ON C.parentId = P.id
LEFT JOIN CTE3 ON CTE3.id = C.id
ORDER BY P.number, ISNULL(CTE3.id,0) DESC, C.letter 

Salida

number  letter
1   A
1   C
2   C
2   B
3   B
3   D

SQL Fiddle

EDITAR

Si sus ids no son secuenciales, puedes cambiar CTE1 y CTE2 así para utilizar ROW_NUMBER()OVER(ORDER BY ID) seq_id .

;WITH CTE AS 
(
SELECT id,ParentID,letter,
ROW_NUMBER()OVER(ORDER BY ID) seq_id,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID) first_element,
ROW_NUMBER()OVER(PARTITION BY parentId ORDER BY ID DESC) Last_element
FROM Child
), CTE2 AS 
(
SELECT c1.id,c1.parentid,c1.letter,c2.parentid as c2parentid
FROM CTE c1
INNER JOIN CTE c2
ON c1.last_element = 1
AND c2.first_element = 1
AND c1.seq_id + 1 = c2.seq_id
)

El resto del código permanece igual.

SQL Fiddle