I have my cards sorted exactly how the TCDB sorts them by year and set. This makes it easy for me to keep everything organized and I can easily find any card I want. All I have to do is go to my collection page, click on sets, and all my cards are physically in that exact same order listed.
I don't know how much work it would be for you, but if you are truly that mixed up, I would personally get all my card organized and then start entering them from scratch. But that's just my OCD talking. I know that may take a lot of time and energy.
I personally do not use any form of "protection" for my cards other than having them stored neatly in white boxes. I don't have a huge collection by most standards, so all of my card I own are currently in three 3200 count full lid BCW boxes. I have 2 for basketball cards and 1 for baseball. However, I am probably going to need to buy a new baseball box soon as I am running out of room. I use BCW Monster Pads to hold the cards upright in box rows that are not complete.
I came to the relaization that the cards in my collection are for me. I don't plan on selling them for profit so I find spending money on protection supplies to be a bit of a waste. I treat and handle my cards nicely and they don't seem to be getting any damage by being naked in a box made for cards. I mean, they come in packs and boxes new without toploaders or penny sleeves. If i ever pull anything that is truly valuable to the point I could sell it and make some serious money then I would probably sell it immediately But I don't see any Honus Wagner cards or Lebron James 1/1 auto patch rookie cards coming my way anytime soon. I do have toplaoders and supplies strictly for transporting cards safely either by mail, or for giving a card to my brother.
When I get new cards, I move all the cards down a row until I get to where the card needs to go. Then I move them all back. It can seem daunting having to move so many cards to make sure a new card goes in the right place and that all the rows are nice and neat again, but honestly it only takes me about 15-20 minutes anytime I add new cards. Of course if it is a new set, it is much easier as it will go near the end.
That being said, if you want to use toploaders, the best storage option for those are BCW shoeboxes. They come in either the standard 2 row design or a Super Shoe Box with three rows. The shoeboxes are designed specifically for toploaders. Penny Sleeved cards can fit in just the normal BCW boxes. BCW also has special boxes for graded cards. (I don't really care for graded cards as I can't put them in my boxes. I have only bought one, it was an Amare Stoudemire Topps Chrome rookie for 99 cents. I had no problem busting it out of the case.)
Jumbo cards and offsize cards? They go in my son's room as decoration or sent out in a trade if they have any type of special value. ( I traded a 1/1 mini card last year). If they aren't standard sized cards, they don't fit in my boxes, so they don't get listed in my collection.
Finally, where do I put my most valuable cards? They are just plain cardboard in the 3200 count boxes like all the others. Again, most of my cards are worth all that much, and the ones that are, I am not selling anyways so it doesn't matter if I have it in a bomb proof case or not.