As I recall, you could get by playing Ultima Online with a 56k modem but it was always laggy. UO displayed something like 30x30 tiles in the client, and each tile could have multiple objects on it, but only non-static objects like player houses, players, monsters and animals, and lootable items would be sent from server to client. Which is why it got terribly laggy when near a bunch of player houses. Pretty much, the land and sea terrain and the permanent buildings / dungeons / etc. were client-side for display but the server would validate whether you could be in that place using the server's copy of the map and statics files.
Anyway, you could easily have 15 non-static objects onscreen as soon as someone walked by, because the game displayed their armor and clothes and weapons on the player model.
This screenshot has around 55 objects that would need to be sent to the client and I would expect little lag. But it's also a very sparse area and many houses would have several hundred items visible per house, and with three times as many houses as in that screenshot. Also you could come upon several dozen people at the bank, each representing 15 items, and also moving and talking, commanding their swarms of chickens to attack each other. There's your lag. Also the game's pace was fairly slow - you couldn't scream across the countryside like with a Terraria grappling hook.
However, it sounds like each Starbound tile would need to be sent to the client - unless it's one of those deals where the client builds the world from a seed and applies modifications afterward. Even so, it sounds like you load more of the world at once than in UO. I could definitely see it being unplayable on a 56k.