It is not clear what you mean with "show up on the network". I will assume that you mean "included in the blockchain" rather than "submitted to the network".
Transactions are spread peer to peer.
When a users sends a transaction, he transmits it to all the peers he is connected to. All these peers will then propagate it to their peers, and the recipients will repeat so again until all nodes in the network have received the transmission.
An exaggerated example
Let's imagine the following (hypothetic) situation:
A has only one peer, who in turn only has only one other peer. Let's say A is connected to the network in a very long chain of weakly connected nodes, which then at some point leads to the "well-connected network".
On the other hand C has ten peers, of which one is very well connected such as a mining pool operator.
Now, when A sends his transaction, it is transmitted to one other node in the network, then a second is notified, in the next step only a third. Obviously, it will take some time until the transaction will spread to the whole network. On the other hand, when C sends his transaction, it is immediately received by 10 other nodes. Each of those sends it to ten other nodes, the mining pool might even send it to hundreds. The network will be notified very quickly of that transaction.
We can see different propagation times, but the effect isn't that huge
According to BitcoinStats, it takes about 0.651 seconds for a transaction to be seen by 50% of the network, and about 2.761 seconds to be seen by 90% of the network.
Also, the above example is exaggerated: Usually, every node will try to connect to several nodes. However, the effect that some transactions will spread faster due to being submitted to well-connected nodes still exists. If a miner finds a block and had already received the transaction of C but not A's. C's might be included in a block before A's transaction. However, the window is pretty small, since the block interval is much bigger than the propagation time.
The effect would be especially pronounced, if A's transaction didn't include a transaction fee, or was non-standard, and therefore not propagated by all nodes.