Boutique Air in California flies PC-12 single-engine turboprops about the size of a Cessna Caravan (photo from Wikipedia).
Their baggage policy currently is as follows:
Note that two of the airports they serve do not allow luggage to be stored for a later flight so if they run out of space you might have an issue.
Most people on these flights are not carrying huge piles of luggage. I carried on a fairly fat backpack with computer inside (four flight segments total) and had no issues (but was not allowed to put it in the aisle). Definitely a civilized alternative to the other option I had for LAX<->Oakland (Spirit Air). The only unfortunate thing is that you have to go through the same TSA nightmare as everyone else.