I am having trouble finding a suitable translation for "man with a van" (i.e., small time delivery driver service). In particular, how would this service be listed in a directory? Can anyone make a suggestion please?
The general term for someone making deliveries is livreur. Although, in the case you describe, I'd go for coursier livreur (definition for coursier, see 2nd tab) which is hinting at the 'small time' part (neither go very far nor transport too big packages).
As a sidenote, the second part is sometimes dropped altogether to have the simple coursier.