It helps if you make your random encounters not look like random encounters. Every encounter with a potential enemy or ally should appear to be an important part of the adventure...

Except when you want to push the players to hurry up because they're dawdling. In that case it's important to make sure they know they are random encounters and they can expect to gain absolutely nothing relevant to the adventure - rather the only thing that can happen is that they lose health/resources. So in such cases make sure the players are aware that you're rolling up an encounter on a table.

(Our GM here is not applying this advice perfectly.)

Transcript

GM: The guards lead you down a corridor of prison cells.
GM: As you walk between the cells a... <roll> tentacle reaches out and grabs <roll> C-3PO.
C-3PO: Eurgh!
Tentacle: {soft voice} Help, you gotta get me outta here!
C-3PO: Not in a position to be taking on quests here, pal.
Luke: No, this could be important!
R2-D2: He rolled a random encounter and a tentacle appeared and attacked Threepio. How do you imagine this ends well?
C-3PO: Well, Mr Green Tentacle, if you let me go I'll see what I can do.
Tentacle: {soft voice} Tell Dr Fred!
R2-D2: Good work, Threepio.
[SFX]: < bippity tong po-fipgi-doip-bedoop >
C-3PO: Yeah, we're no suckers.