I had used mudkip as main pokemon and charmander as partner. It was a beast combonation

I didn't play through the whole thing, but my main character was Mudkip and my partner was Pikachu.

Don't limit this to Red because Blue is the same in terms of starters.
On Blue I was a Treeko and had Torchic as a partner
On my Red game I was an Eevee (because I was tired of being "Quirky") with a Cyndaquil partner
On the Red game that was given to me that is from somebody else, the main character was Machop and the partner was Charmander.

It's difficult to be a grass type in the beginning, but it gets easier.
Eevee is difficult to use before she evolves.
Machop is someone hard for most boss battles.
Fire types have the advantage of lava walking, but it's dangerous, as with water types on water, when you want to move to where your partner is (can cause warping). 

I'd imagine that since water would only have type match up issues in the beginning, which has grass types often, would benefit when going through the fire parts in the middle of the game, and would have good defense against its own type, water, after the end of the story, that it may be a nice choice.

On Blue I was a cyndaquil, and my partner was a Chikorita Ahh nostalgia

I was either cyndaquil or mudkip, mudkip most of thhe time. And my partner was almost always treeko or if i was cyndaquil it was... some water type, I cant remember.

I has cubone and cyndaquil, making the zapdos, moltres, and groudon battles much easier. But the Rayquaza battle annoyed me to no end...

I made many different teams, but I'm going to name the one I'm working on now in Blue. I am Squirtle and my partner is Cydaquil.

I am at Ninetales at the moment, and my other Pokemon are: Absol and Zigzagoon.

My team in Red Rescue Team is I think......... Charmander as my main....... and........ Pikachu as my partner.

My main character on my first play through was charmander. Pretty cool I guess.

For my partner, I actually put some thought in. Okay, not really. I had never heard of Treecko, or I didn't remember it, so I chose him, just because I wanted to.

I chose him over Mudkip probable because I wanted him to cover my weaknesses, instead of him covering mine. I think I made the right choice. I think this thread may inspire me to pick up my GBA, and start a new game. I guess sometimes, inspiration can come from the craziest, or most normal places. It just depends on whether or not you look for it.

In Red, I have Cubone and Treecko...
In Blue I have Charmander and Pikachu

mine was cyndaquil and squirtle. cyndaquil learnt really good moves but cubone would be the best choise simply because it can learn boomerang and moves that hit more than once are overpowered in thin game

In red rescue team: Cubone and Bulbasaur
In blue rescue team: Machop and Mudkip
In time: Chikorita and Cyndaquil
In darkness: Torchick and Turtwig
In sky: Phanpy and Shinx

My main was charmander my partner was squirtel I managed to beat the hole game caught all the legendairies the hardest one to recruit was deoxys

Machamp as my main and as by sidekick Charmander just couldn't resist.  I love Machamp.