Mhh... mi sa che questa è l'unica soluzione possibile... Puoi provare però ad usare la tecnica della Variable Enregistration: in pratica, crei una variabile temporanea di tipo DataTable e ci copi dentro il valore della tabella corrispondente. Dato che viene dichiarata come interna a una procedura, il suo valore viene memorizzato in aree di memoria temporanee a più alta accessibilità, in modo da velocizzare leggermente il processo. In seconda istanza, prova ad usare un ciclo iterativo per oggetti e non per indici: in questo modo, ottieni direttamente l'istanza della riga senza doverla prelvare con l'indice ad ogni ciclo.
codice:
Dim Table As DataTable = Titoli.Dataset.Tables("Titoli").Clone

For Each Row As DataRow In Table.Rows
  txtTitoli.AutoCompleteCustomSource.Add(Row("Nome").ToString)
Next
Viene anche più leggibile, ma ricorda che in questo modo la velocità viene sì aumentata (e non di molto), ma ne risente l'uso della memoria, poichè copi un dato assai vasto. Decidi tu come fare in base alle tue esigenze.