In Pokemon Yellow, there are a few times when you'll be asked to trade Pokemon with an non-player character. Some of the Pokemon available prove advantageous against nearby Gyms or story points, and some are only available in this version through such trades.

Route 2: Mr. Mime

Location: Route 2

Method:
The first in game trade you'll probably encounter is this one outside Diglett's Cave on Route 2. A man will offer you his Mr. Mime for your Clefairy. Though Clefairy is hard to find, Mr. Mime doesn't appear in the wild at all which makes this a good deal. Mr. Mime has decent Special and Speed but poor physical stats and HP.

MILES
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Clefairy
Route 5: Machoke

Location: Route 5

Method:
The underground tunnel (north exit) has a trainer who will trade Cubone for Machoke. The Machoke will evolve into Machamp right after the trade, giving you an extremely tough Fighting-type early in the game. As soon as you can catch Cubone it is recommended you make this trade.

RICKY
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Cubone
Route 11: Dugtrio

Location: Route 11

Method:
Lickitung is only found in the Unknown Dungeon or by trading for one in Red or Blue. It's easier to level up a Diglett or catch a Dugtrio if you really want one on your team.

GURIO
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Lickitung
Route 18: Parasect

Location: Route 18

Method:
You can find both Pokemon in the Safari Zone. It's actually easier to find a wild Parasect than a wild Tangela in there so just grab one while you're getting HM03.

Spike
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Tangela
Cinnabar Island: Rhydon

Location: Cinnabar Island

Method:
Rhydon can be a pain to catch in the wild or train a Rhyhorn to get. You can Surf for Golduck on Route 6, so if you really want a Rhydon the trainer in the Cinnabar Island lab by the Pokemon Center will gladly trade for a Golduck.

BUFFY
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Golduck
Cinnabar Island: Dewgong

Location: Cinnabar Island

Method:
Growlithe for Dewgong seems like a good deal, except Dewgong are found in the Seafoam Islands. However, you can catch a Growlithe in the Pokemon Mansion to trade if you don't feel like making the trek.

CEZANNE
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Growlithe
Cinnabar Island: Muk

Location: Cinnabar Island

Method:
The final trade on Cinnabar Island is rather trite. Kangaskhan is only found in the Safari Zone and is rare to boot, though Muk is available literally up the road from the lab in Pokemon Mansion. You may as well save yourself the effort and catch one while looking for the gym's key.

STICKY
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Kangaskhan