I've had applications using Acces (97) FE and BE where a form was linked to a table with about 1.5 million records (and each record was a decent size, not, for example, just 2 or 3 integer columns). They worked very well without the long waits you mention.
I wonder if every table (at least those of any size) has a primary key, particularly a numerical one (text primary keys, especially those involving multiple text columns, should be avoided if at all possible).
Another question is if the network connection is working correctly. I have encountered situations where the network connections were lousy, even though they should have been fast enough (and were sometimes).
If you can set up one drive letter as mapped to the network server where the BE is stored, linking through a drive letter can be quicker than by using UNC (of course, you then lose the flexibility of UNC linking).
I would strongly suggest that you avoid replication if at all possible. Obviously, for the situration of a dial up (as Little Smudge mentions), these really is no option. But ISDN should be quick, I believe, so that would not be appropriate for replication. Replication can be a nightmare to administer. And if any tables require manual intervention when updating through replication you have created a monster.