In the spirit of pub names, here's a meta list of French café typical names, though most of them don't have much historical background behind them, or are just called by the name of the street.
The absolute classics, you'll have one of those in every French town:
See also Hôtel Beau Rivage
Interestingly named cafés in Paris:
(to be continued)