Is it "between First and Main Streets" or "between First and Main streets?
I do have an actual answer for this—which I will provide later—but I want to first make an observation.
Sometimes, trying to simplify something actually overcomplicates it. This is such an example.
Rather than worrying about the capitalization in your sentence, I would rephrase it one of two ways:
1) Between First Avenue and Main Street.
2) Between First and Main.
The first version uses the full name of each street, while the second is the equivalent of just using "first names." Both would be understood.
Note that I am assuming these are streets in New York. It's possible that you are talking about a different city where there actually is a First Street (and a Main Street). If that's so, then replace First Avenue above with First Street.
As for the technical answer, the proper names of the streets are First Avenue and Main Street.
You could also have Maiden Lane, and Victory Boulevard.
(From a quick search, it seems that New York's famous Broadway actually has no suffix at all—that is its full name.)
While it's true that Maiden Lane is a lane and Victory Boulevard is a boulevard, the most common generic noun for referring to them is street. Not knowing their names, somebody would most often point at one and ask What street is that? (It's far less likely that they would ask What boulevard is that?)
So, if you are going to drop the "last name" of these streets, then when you add the word street after naming them, you are adding the noun rather than part of a name.
Your example sentence would actually be formed from 2) above—with the noun streets appended to it. Since the noun is not part of a proper name, it is in lowercase.
Between First and Main streets.
It doesn't matter if First or Main is actually a street, avenue, lane, boulevard, or anything else. Here, it's just the common noun that's being appended to refer to them collectively.
Having said all of that, it does sound awkward—and for the very reason that you have pointed out. So, I would avoid the complication and just rephrase it.