Mi voto: Yibuti (Djibouty)

Cualquier ciudad de la costa del Mar Rojo sobre Eritrea, Djibouti o Somalilandia (norte de Somalia) puede ser candidata: Andan entre los 30-31º de media anual. No sé si también alguna de la costa del Mar Rojo sobre Yemen o inclusive del sur de Arabia Saudí (Gizan supera los 30º de media anual, creo). Además son todas ciudades con una humedad tremenda, debe ser el infierno vivir por allí.

Algunos datos de Yibuti
Temperatura media: 30ºC
Temperatura media julio: 41ºC
Temperatura media  enero 23ºC
http://www.climatetemp.info/djibouti/

Cuidado que los 41º son la media de las máximas (de julio) y 23º la media de las mínimas (de enero, el mes más fresco  ), creo que las medias de los meses respectivos son de 36 y 26º respectivamente.
3200 horas de sol al año en una ciudad ubicada a 11 grados de latitud, es una locura.

Massawa (Eritrea) 29,4º - 184 mm
Assab (Eritrea) 30,3º - 58 mm
Djibouty City (Djibouti) 30,0º - 131 mm
Berbera (Somalia) 29,9º - 53 mm
Adén (Yemen) 29,8º - 61 mm
Gizan (A. Saudita) 30,7º - 42 mm

El dato de Gizan (16º 53' N sobre la costa saudí del Mar Rojo) no deja de ser interesante.

Links:

http://en.wikipedia.org/wiki/Massawa#Climate
http://en.wikipedia.org/wiki/Asseb
http://en.wikipedia.org/wiki/Djibouti_(city)#Climate
http://en.wikipedia.org/wiki/Berbera#Climate
http://en.wikipedia.org/wiki/Aden#Climate
http://en.wikipedia.org/wiki/Gizan

La tabla de Djibouti me parece algo dudosa ya que marca récords históricos de 54º que a mi me parecen erróneos. Da una T media algo más baja que la del link que subiste, así como una HR mucho más alta (69 % en promedio). Tremenda Massawa también con 70,3 % de promedio en el año. De las otras ciudades no encontré datos.

Claro que los tiros tienen que estar por ahí, el mar rojo en su parte sur recibe una radiación solar brutal durante todo el año, el estar rodeado de desiertos asegura poca humedad en niveles medios altos por lo que la formación de nubes y lluvia que atemperen algo las temperaturas es escasa y las altísimas temperaturas de este mar cerrado que intercambia  poca agua con el océano Indico hacen que la humedad en superficie se mantenga muy alta por lo que el enfriamiento nocturno sea menor.

Saludos 

Las ciudades ribereñas del Golfo Pérsico tampoco andarán muy atrás, Kuwait, sur de Irán, Emiratos Árabes.....

Pero esas ciudades del Golfo Pérsico están más al norte que las del sur del Mar Rojo, la mayoría al norte del trópico de Cáncer. Entonces - al menos si hablamos de medias anuales - son más frescas, ya que tienen un pequeño "invierno", con temperaturas medias en enero que van desde los 12-13º en Irán y Kuwait hasta los 21º en Mascate, Omán. En cambio las ciudades del sur del Mar Rojo, entre 10 y 16 grados de latitud, no bajan de 24-26º el mes más fresco. Lo que sí, los veranos en la costa del Golfo Pérsico superan por unos pocos grados a los del Mar Rojo.
Como muestra: nuevamente temperaturas medias y precipitaciones.

Mascate (Omán) 28,3º - 94 mm
Abu Dhabi (EAU) 28,0º - 109 mm
Dubai (EAU) 27,8º - 89 mm
Doha (Qatar) 27,1º - 75 mm
Manama (Bahrain) 26,2º - 71 mm
Dammam (A. Saudita) 26,3º - 67 mm
Kuwait City (Kuwait) 27,1º - 116 mm
Abadan (Irán) 25,0º - 193 mm
Bandar-Abbas (Irán) 26,9º - 240 mm

Y podemos agregar a la ciudad de Salalah (Omán) que se encuentra fuera del Golfo Pérsico sobre la costa sur de la Península Arábiga, y que es afectado marginalmente por los vientos del monzón de verano lo cual refresca considerablemente sus temperaturas en esta estación (a pesar de estar a una latitud varios grados menor a Mascate y otras ciudades del país, y también a nivel del mar, mucha gente huye del calor allí).

Salalah (Omán) 26,3º - 109 mm

Links:

http://en.wikipedia.org/wiki/Muscat,_Oman#Climate
http://en.wikipedia.org/wiki/Abu_Dhabi#Geography_and_climate
http://en.wikipedia.org/wiki/Dubai#Climate
http://en.wikipedia.org/wiki/Doha#Climate
http://en.wikipedia.org/wiki/Manama#Climate
http://en.wikipedia.org/wiki/Dammam#Climate
http://en.wikipedia.org/wiki/Kuwait_City#Geography_and_climate
http://en.wikipedia.org/wiki/Abadan#Climate
http://en.wikipedia.org/wiki/Bandar-Abbas#Climate
http://en.wikipedia.org/wiki/Salalah#Climate

Otra ciudad muy cálida sobre el Mar Rojo es Jeddah, ligeramente al sur del trópico de Cáncer. Su media anual es de 27,7º con una precipitación anual de 61 mm. Lamentablemente no encontré ninguna estación intermedia en la costa entre Gizan y Jeddah. De cualquier manera, es más "fresca" que Mascate que se encuentra casi dos grados de latitud más al norte.

http://en.wikipedia.org/wiki/Jeddah#Climate

Fuera de los mares Rojo y Pérsico estoy casi seguro de que las ciudades del noroeste de Venezuela son las que llevan la delantera. Un ejemplo es la ciudad de Coro (Maracaibo creo que no cuenta ya que no está sobre la línea de costa). Coro tiene una media anual de 28,6º y 411 mm de precipitación anual, prácticamente los mismos datos que Maracaibo.

http://en.wikipedia.org/wiki/Santa_Ana_de_Coro#Climate

Entre 28 y 28,5º ya podemos encontrar zonas costeras tropicales y ecuatoriales más variadas (Madrás, Yakarta, Ho-Chi-Minh City, varios puntos de la costa oeste de Centroamérica, etc.)

Un poco más al norte, en la costa de Sudán hay también datos interesantes:

Puerto Sudán (19ºN) 28,4ºC - 76mm
http://es.wikipedia.org/wiki/Puerto_Sud%C3%A1n

Maracaibo, en Venezuela, tiene una media anual de 28,5ºC con una HR que casi siempre supera el 85-90%.

Madrás en la costa suroriental de la India también alcanza una media de 28,5ºC