I used a Widelux with TMax 100 film...got beautiful 16x20's, in that they were sharp, not grainy, etc. They held up really well.
Look, people have used 4x5 or even 8x10 for 'street' photography. With film today, you can easily do it in 35mm. As with so many other threads, it ultimately comes down to your vision, your preference. 35mm is a fine start, although 645 or 6x6 is viable, too FWIW.