To see why use FullForm on both data and data2:

data // FullForm
(* List[1, 2, 5, 3, 4, 7, 6] *)

data2 // FullForm
(* List[Style[1, RGBColor[1, 0, 0]], Style[2, RGBColor[1, 0, 0]],  
  Style[5, RGBColor[1, 0, 0]], Style[3, RGBColor[1, 0, 0]], 
  Style[4, RGBColor[1, 0, 0]], Style[7, RGBColor[1, 0, 0]], 
  Style[6, RGBColor[1, 0, 0]]] *)

data2 is not a list of numbers.

As Jim stated, they are not a list of numbers,

You can separate the parts of the list into two columns, the first containing the actual number (the one you want to sort) and the other containing the color:

In[1]:= data2[[All, 1]]
Out[1]:= {1, 2, 5, 3, 4, 7, 6}

In[2]:= data2[[All, 2]]
Out[2]:= {RGBColor[1, 0, 0], RGBColor[1, 0, 0], RGBColor[1, 0, 0], RGBColor[
 1, 0, 0], RGBColor[1, 0, 0], RGBColor[1, 0, 0], RGBColor[1, 0, 0]}

The function MaximalBy allows you to specify a function the result of which will be the basis for your maximum, you can write:

MaximalBy[data2, First]

Which is equivalent to:

MaximalBy[data2, #[[1]]&]

i.e. it finds the maximum by looking at the first entry of each row (this is where you keep your values). Similarly, you can use SortBy to sort your colored lists.

Regards, Patrik