Trading with non-player characters makes a return in Crystal. Only one Pokemon in the game is only gotten via trading this time around, and you won't encounter it until Kanto. Some of the trades offer rare Pokemon for common Pokemon, and some offer rare Pokemon for rare Pokemon. It's up to you whether you want to make the trades or not though so choose wisely.

Violet City: Onix

Location: Violet City

Method:
The first trade you are offered is made in a home in Violet City. This trade offers you a strong Onix in exchange for the rather common Bellsprout, which can be found outside of Violet City in the grass. Onix is great for the first and second gyms and will prove useful in the fourth, seventh, and eighth after it evolves into the Steel-type Steelix. Definitely a great alternative to Geodude.

ROCKY ♂
Level ??
OT:KYLE
ID:48926
Hold Item:
Bitter Berry
  
  
Trader requests a Bellsprout
Goldenrod City: Machop

Location: Goldenrod City

Method:
A trainer offers you their female Machop in exchange for Abra inside the Goldenrod City Department Store. Abra can be caught on the route south of Goldenrod City, whereas Machop can't be found until you reach Mt. Mortar. Machop is very handy against Whitney's Miltank, Jasmine's Steelix, and Pryce's Piloswine, so consider this trade.

MUSCLE ♀
Level ??
OT:MIKE
ID:37460
Hold Item:
Gold Berry
  
  
Trader requests a Abra
Olivine City: Voltorb

Location: Olivine City

Method:
This trade is a bit useless. Magnemite can do everything Voltorb can and has Steel-typing for added protection, and is caught near Ecruteak City anyways. If you really want to use Electrode, wait until you reach the Team Rocket Headquarters and can catch a Level 30 one.

VOLTY
Level ??
OT:TIM
ID:29189
Hold Item:
PrzCureBerry
  
  
Trader requests a Krabby
Blackthorn City: Dodrio

Location: Blackthorn City

Method:
Kind of a useless trade, unless you really don't want to wait until after you beat Clair to get a Dodrio. Your Dragonair has to be female. It's not really worth it considering Dragonair will be more help against Clair than Dodrio will be.

DORIS ♂
Level ??
OT:EMY
ID:00283
Hold Item:
Bitter Berry
  
  
Trader requests a female Dragonair
Pewter City: Xatu

Location: Pewter City

Method:
This is a cool trade. Xatu can be hard to get if you missed Natu earlier at the Ruins of Alph, plus PAUL holds the ever-rare MYSTERYBERRY. Haunter can be caught in Rock Tunnel so pick an extra up.

PAUL ♂
Level ??
OT:CHRIS
ID:15616
Hold Item:
Mystery Berry
  
  
Trader requests a Haunter
Power Plant: Magneton

Location: Power Plant

Method:
This one is all up to personal preference and what you have. Trade one trio of the same Pokemon for another trio of the same Pokemon. Neither one is particularly hard to get at this point in the game and both have awesome abilities.

MAGGIE
Level ??
OT:FOREST
ID:50082
Hold Item:
Mystery Berry
  
  
Trader requests a Dugtrio
Route 14: Aerodactyl

Location: Route 14

Method:
The only Pokemon exclusive to trades in these games is Aerodactyl. However, you'll need to trade the elusive Chansey to get it. It's a decent trade off unless you like Chansey, and Aerodactyl can provide some great late game support, ripping through Erika and Blaine's teams without a problem.

AEROY ♂
Level ??
OT:KIM
ID:26491
Hold Item:
Gold Berry
  
  
Trader requests a Chansey