Ciao,
diversi consigli per te .
Innanzitutto io cambierei la query con questa:

$query = "select distinct(regione) from vini where 1 order by regione ASC";
$result = mysql_query($query);
$i = 0;
while($dati = mysql_fetch_array($result){
echo "Regione".$i.": ".$dati[regione]."
" ; // o anche $dati[0]
$i++;
}

Beh, il testo stampato su schermo poi te lo modifichi come vuoi tu
Non ho testato il codice ma dovrebbe andare.
Per ricavarti le provincie ecc.. basta che sostituisci il nome del campo tra le parentesi.

Un'altra cosa, questo è un consiglio a titolo di organizzazione del database, in futuro, quando nei record devi inserire nomi di regioni o provincie, per semplicità, ti consiglierei di crearti 2 ulteriori tabelle, una chiamata regioni e l'altra provincie ed inserirle al loro interno, in modo tale da dover inserire solo l'id univoco che indica la regione/provincia nei record dei vini e non il nome completo.

Spero di esserti stato di aiuto.
Bye!