“As you can see, I’m a pretty average student”
You aren’t. Why do posters say this when it’s not the case?
Anyway, for your interest in pre-med, this online list isn’t bad for generating ideas for colleges to research further: “The Experts’ Choice: Colleges with Great Pre-med Programs.”
For education, your search should extend beyond schools with an education major. A common route is to major in your field of interest, then pursue a master’s in education. Minoring in a field such as education studies as an undergraduate will, however, give you valuable early experience.