As a Junior at Berkeley who's had some internship experience, let me add me two cents worth.
Definitely start looking for an internship during your freshman year. Chances are almost nobody will call you back, you won't get many interviews, and the ones you do get you won't be able to answer anything, but all you need is just to get one person to agree and it'll make your resume look infinitely better for the following years.
Startups are definitely a good option for an internship. What I see a lot of the time, especially here at Cal, is that nobody wants to work anywhere besides Google, Apple, Microsoft or Facebook. People don't bother with any company that doesn't have a huge name and since many of these students don't have any prior work experience before applying to these tech giants, they get rejected. I think that's a huge mistake. I learned more from my summer working at a startup than a years worth of schooling (and it's not bad learning while being paid).
One last note, GPA doesn't seem to matter as much as work experience. While it can never hurt to have a good GPA, I've been on dozens of interviews and not once have I been asked for my GPA.