I doubt you have "way too much data" in public folders. Public folders are stored using the same ESE engine that stores mailboxes, and I've seen Exchange 2003 installations with upwards of 100GB mailbox databases (though, arguably, they performed very badly compared to newer versions of Exchange, they did work fine).
Diagnosing your "replication issues" is something that I'd need more information to help with, so I won't even attempt to tackle that here. What I will do is offer some commentary re: the rest of your question.
Each Mailbox database has a "Default public store" specified in the properties of the Mailbox database. Outlook will attempt to access public folders stored in that public folder store first. You can host multiple replicas of a public folder in different public stores (to load-balance client access and to provide replicas in physical locations that have poor WAN connectivity) or you can have a few (or one) public stores that you aggregate client access into. Which is "right" depends on the hardware you're hosting the stores on, the access patterns of your users, and your network topology.
When a user attempts to access a public folder that doesn't have a replica on their default public store Outlook will request a referral from the user's default public store to another public store that does host a replica. The referral algorithm takes into account connectors between routing groups (and is described in detail in that linked article) but, for your purposes I suspect all your servers are in the same routing group, which means that Outlook will end up randomly choosing a replica out of all the servers that contain replicas of a given folder.
You absolutely can have a single public folder store w/ no replication that all your clients will use. You'll just need to set the default public store on all your mailbox databases to accomplish that. Given that Exchange 2003 is a 32-bit application you might be able to realize a caching advantage to hosting all your public folders on a single server that doesn't host any mailboxes. Since you have mailboxes hosted on all four servers, though, you'll probably be better off hosting public folder replicas on all four servers and fixing whatever your replication issues are.
Within a LAN public folder replication should be happening fairly quickly. If the servers are severely overtaxed, or if you've got configuration issues it could take much longer. You might consider posting a separate question with details about your "replication issues" to get some help on that front.