I would recommended at least 100 kilobytes/s (800 kilobits/s dedicated upload for a reasonably reliable server). To prevent congestion you would want an actual connection upload speed of 300-400 kilobytes/s (2.4-3.2 megabits/s). This means that only cable or fibre optic ADSL or better users can really run servers. More upload is needed for big maps so that they can be downloaded in a reasonable time. Also it is highly unlikely you will get a good server on any form of wireless connection, be it mobile or LAN.
It is important that your connection is not congested and reliable. The synchronization used by Simutrans is quite poor so any form of unreliability delivering packets between server and clients can cause them to go out of sync.