In Pokemon Red and Blue, 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 these versions 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 Abra. Though Abra can be hard to catch, Mr. Mime doesn't appear in the wild at all, making this a good deal. Mr. Mime has decent Special and Speed but poor physical stats and HP.

MARCEL
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Abra
Route 5: Nidoran

Location: Route 5

Method:
The underground tunnel (north exit) has a trainer who will trade Nidoran for Nidoran. This trade is recommended in Red where male Nidoran are plentiful but female are rare. Blue version offers a common female Nidoran but rare male Nidoran, thus making it a useless deal, unless you want an outsider Pokemon that grows quicker.

SPOT
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Nidoran♂
Route 11: Nidoran

Location: Route 11

Method:
Same as the Nidoran trade, except this deals with the evolved forms.

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

Location: Route 18

Method:
Lickitung can only be obtained in this trade. Though Slowbro are uncommon, it is a decent trade off in terms of Pokedex completion. Despite this, Slowbro are much more useful in battle than Lickitung, who doesn't evolve in this game and has very mediocre stats. The owner is found in the gate upstairs on Route 18.

MARC
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Slowbro
Cerulean City: Jynx

Location: Cerulean City

Method:
The house next to the Pokemon Center is home to an elderly man who will trade his Jynx for your Poliwhirl. As with Mr. Mime, Jynx has great Speed and Special but unremarkable HP or physical stats. However, it gets the very rare Ice Punch move and can learn Ice Beam. This in game trade exclusive Pokemon is well worth the Poliwhirl.

LOLA
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Poliwhirl
Vermillion City: Farfetch'd

Location: Vermillion

Method:
This trade offers Normal/Flying-type for Normal/Flying-type. Farfetch'd can't be found anywhere else in the game, though in terms of brute force you're better off evolving the Spearow and using that.

DUX
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Spearow
Cinnabar Island: Seel

Location: Cinnabar Island

Method:
The Cinnabar Island laboratory contains a couple of people who'd like to trade with you. These trades are mostly useless as you can catch all of the Pokemon offered in the wild at approximately the same difficulty. Ponyta for Seel is only helpful against Blaine if you can't be bothered to go to the Seafoam Islands to find one yourself.

SAILOR
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Ponyta
Cinnabar Island: Electrode

Location: Cinnabar Island

Method:
The second trader in the lab wants a Raichu for Electrode. Both are found in the Unknown Dungeon so save yourself the Thunderstone and pass this up. Interestingly, after this trade, he notes that the Raichu went and evolved, referencing the trade in the Japanese Blue game

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

Location: Cinnabar Island

Method:
Don't bother. It's easier to just catch Tangela south of Pallet and this one provides no addition help

CRINKLES
Level ??
OT:TRAINER
トレーナー
ID:Random
  
  
Trader requests a Venonat