Los personajes aleatorios son personas a las que puedes conocer en distintos puntos de la ciudad luego de completar determinadas misiones de la trama principal. Este reto forma parte del 100% del juego y aporta un 5% a tu partida. Los personajes aparecen señalados en el mapa normalmente con el icono de una persona de color blanco, pero éste torna azul cuando estás lo suficientemente cerca de alguno de ellos. Puedes consultar la cantidad de personajes que has encontrado desde Estadísticas > Puntuación > Personajes aleatorios encontrados cuando el juego está en pausa. Ten en cuenta que, si bien son 3 los personajes que figuran en las estadísticas, en realidad son 5 encuentros los que debes completar. Otra cosa a tener en cuenta es que, en el caso de Arnaud y Margot, el segundo encuentro no aparece inmediatamente luego de terminado el primero, así que puedes ir completando otro personaje u otro tipo de misión para que pase el tiempo y se habilite el segundo encuentro de cada uno de ellos.
En el mapa que hay a continuación se encuentran señalados los 5 encuentros de los 3 personajes aleatorios.
Conocerás a Arnaud frente al local Viendemorte, ubicado en la esquina de Hematite St. y Columbus Av., en la zona de El Triángulo. El personaje aparece en dicha ubicación luego de completar la misión "Practice Swing" de Tony Prince.
Arnaud es un hombre proveniente de Francia que critica a la televisión norteamericana y lamenta la cultura actual de la sociedad francesa. Dice haber llegado a Liberty City con el único fin de estar con mujeres y consumir drogas. Luego de tener una charla con Luis, le pide que lo lleve al Barrio Chino, donde hay una masajista que lo está esperando.
Consigue un vehículo y espera a que Arnaud suba contigo. Luego, conduce hacia el punto señalado en el Barrio Chino, donde está el balneario de masajes. Una vez en Amsterdam Lane, aparca junto a los carteles amarillos con la leyenda "High-End Massage Spa" para completar el encuentro.
Esta vez Arnaud está tirado en la acera de Vía Folsom frente a la tienda Pawnbrokers, en Fortside, con varios golpes en la cara. Arnaud estuvo consumiendo opio chino y quiso tener relaciones con unas prostitutas brasileñas, pero su chulo comenzó a golpearlo y luego le robó la billetera.
Consigue un vehículo y conduce hacia Bronco Street para ayudar a Arnaud a recuperar su cartera. Cuando llegues al lugar, veras al chulo alejándose en su coche. Intenta embestir el auto del objetivo señalado con rojo en el radar para detenerlo, lo ideal es que lo arrincones contra alguna pared o poste para forzarlo a bajar del vehículo y acabar con él; también puedes chocar el coche y dispararle para conseguir que el chulo salga. Si el objetivo se aleja demasiado, lo perderás de vista y no podrás recuperar la cartera de Arnaud. Cuando hayas eliminado al chulo, recoge la billetera que deja caer.
Finalmente, saca a Arnaud de la zona de Bahía Chica y llévalo a un lugar relativamente seguro en Vía Folsom, Fortside, frente a la joyería.
Margot aparece sentada sobre unos escalones junto al club Hércules en la esquina de Lorimar St. y Galveston Av., en la zona de Purgatorio. Este encuentro está disponible después de la misión "Bang Bang" de Tony Prince.
La chica simula haber encontrado a Luis de casualidad, aunque es evidente que ha estado persiguiéndolo. Margot es una ex-novia de Luis, se trata de una chica depresiva y obsesiva que aún está enamorada de él, a pesar de que su relación terminó un año atrás. Margot le reclama a Luis por las llamadas y correos electrónicos sin respuesta, y luego le muestra un frasco de pastillas vacío diciendo que ha tomado 37 sedantes y 15 pastillas para dormir. La chica comenzará a actuar como descompuesta, y le pedirá a Luis que la lleve al hospital.
Consigue un vehículo y espera a que la ex-novia de Luis suba. Ahora conduce rápidamente hacia el hospital ubicado en Jade St., Easton. para que los médicos puedan atenderla antes de que muera por los sedantes.
El segundo encuentro con Margot tiene lugar en el Muelle 45, en Bus Lane, Lonja Sur. Debes subir por las escaleras hasta el nivel superior y dirigirte al balcón que hay frente al río para encontrar a la chica.
La chica está parada sobre un aire acondicionado al otro lado de la baranda, y amenaza con suicidarse ya que Luis no quiere casarse con ella. La chica muestra una carta que escribió, en la cual dice que Luis tiene la culpa de que muera. Cuando Luis intenta darle la mano, la chica se deja caer y muere instantáneamente.
Los testigos que hay alrededor comenzarán a gritar diciendo que Luis la ha empujado. Debes correr para alejarte de las personas que te persiguen y que intentan atacarte. Debido a la alerta dada por la gente, enseguida llegará la policía y tendrás un nivel de búsqueda de 2 estrellas. Consigue un vehículo y aléjate de la zona de búsqueda policial para finalizar el encuentro.
Daisy aparece sentada junto a la barra del club Maisonette 9 en el horario de apertura, es decir entre las 21:00 y las 06:00 hs. Este encuentro se habilita tras completar la misión "Clocking Off" de la mamá de Luis.
Daisy es una chica británica que alguna vez tuvo relaciones con Luis, pero parece no recordarlo bien ya que lo llama por el nombre de Steve ó Leslie. Tampoco recuerda bien a Tony, debido a que lo llama Terry. Se trata de una adicta a la cocaína que le miente a Luis respecto a por qué nunca más lo llamó. En medio de la charla, la chica recibe un llamado de alguien avisándole que Chris Hunt, un homosexual con quien tuvo un encuentro sexual, la ha filmado en su encuentro y planea publicar el video en internet para que la gente no tenga más sospechas sobre su sexualidad. Daisy le pide a Luis ayuda para evitar que eso suceda y así evitar problemas con su novio Bertie.
Consigue un vehículo y espera a que la chica suba contigo. Ella dirá que el famoso actor siempre está publicando lo que hace a través del sitio web Bleeter, y así será posible saber dónde se encuentra. Enseguida Chris enviará un mensaje con una foto desde un baño con vistas a Middle Park, así que dirígete hacia la zona residencial para intentar encontrarlo. Antes de que puedas llegar, otro mensaje será subido donde habla de su sastre llamado Marcus. Conduce en dirección a la tienda Perseus, ubicada en Pyrite St., Middle Park Este. Mira alrededor y espera al próximo mensaje enviado por Chris. En esta ocasión, Daisy supone que el actor se encuentra en el restaurante de mariscos llamado Squid Row. Cuando llegues a Bismarck Av., Easton, Chris enviará un último mensaje contando que está yendo al estreno de su nueva película en Cruce Estrella. Finalmente encontrarás al actor en Denver-Exeter, allí está mirando una pantalla gigante donde hizo publicar el video en el que aparece Daisy. La chica se lamentará por lo sucedido y habrás completado el encuentro.