No se que tienes planeado en hacer en PHP (un supercodigo XD) para darle tanta importancia a la complejidad de los algoritmos y de las funciones de PHP.
Para tener en cuenta la complejidad estariamos hablando de vectores muy grandes(millones), por lo que mi primera propuesta anterior no seria tan mala, las posibilidades de que caiga en el ultimo serian de 1/millones. De todas formas a ver esta:
Código PHP:
$i = array_rand($citas);
$valor = !empty($citas[$i]) ? $citas[$i] : $citas[$i-1];
A ver esta. Solo usas el array_rand una vez, en caso (infinitesimo) de que caigas en la posicion vacía, escogera el valor anterior. Esta vez el "problema" seria de que la ultima posicion tendria una pequeña ventaja de ser seleccionada (2/millones de posiblidades XD).