Velocità di queste due query

[.Kurt]

come scritto da Kurt con count conto solo le righe invece con l'altra
query estraggo inutilmente tutti i record (anche se questi fossero
migliaia) o sbaglio?

A parte questo, quando devi contare il numero di occorrenze di una lista tu al database non richiedi una parte di quella lista per contare i risultati, chiedi direttamente il numero delle righe coinvolte. Recuperarle tutte per poi e contarle tu stesso è ridondante.

A questo punto, potrei ottenere il tutto su una sola variabile come la prima query senza usare mysqli_fetch_array?

da php 5.4, $tot_utenti = mysqli_fetch_array(mysqli_query($db, "SELECT COUNT(utente_id) AS TotUtenti FROM utenti WHERE..."))['TotUtenti'];

Ma una cosa del genere è illeggibile. Con PDO:

$count = $pdo->query('SELECT COUNT(*) FROM ...')->fetchColumn();