For Each game (gyms):
RBY: Misty was definitely the most difficult w/o bulbasaur.
GSC (I only played HG): The normal type gym because of Miltank
RSE: It's been a very long time, but the fire gym with torkoal was the biggest issue with me (started with Treeko) that i remember.
DPP: In Diamond, the Ghost-gym. DPP - Water type with Floatzel and Gyarados.
BW/BW2: Elesa's gym for sure. It's the only Gen 5 gym I actually blacked out on, playing W2 challenge mode. I didn't have any fool-proof counters though (like trapinch).