Try a map with lots of ocean and send clippers (appear in 1837, use six passenger and one mail module) from a central hub to every town. Running costs are so low that a 50km route with even 5-10 passengers per trip can be profitable. Then build "feeder" lines running coaches to your ports. Most of them lose money, but the increased traffic on your ship routes makes more than up for it. But you need to expand quickly and use at least 2-4 ships on each route.
Fortunately, sailing ships cost practically nothing. I haven't tried early steamships yet (it's 1861 in my game), but their price is insane: 10-30 times of what a clipper costs. Plus twice the cost for the shipyard.
Before clippers appear, it should be very, very hard to survive on passenger/mail transport alone.
Rail in the 1860's is a sure money loser. Narrowgauge networks less so, but still bleeding money.