The committee actually advised you to find a prof that taught a smaller class? Eep!
Yes they have to have taught you ... so they can comment on how well you handle your academics etc.
Well trying to make an impression to a prof who teaches a huge class may be kind of hard (i'm not saying it can't be done). But if all your classes are huge, then just make small talks everyday after class, he/she's bound to remember you that way. I find that though, by upper year, the classes tend to be smaller and it's easier to approach them that way.
And if you are going to ask a prof to write a letter... make sure you actually did well in that class haha. I had a meeting with a prof once and he totally looked up my GPA and everything before I even showed up... I guess when the professor doesn't remember you that well, numbers and grades still mean a lot.