SM465 or SM420 are the two easiest/cheapest swaps for lower gears. If you get a 10 spline version of either trans and a plate adapter you're good to go. Whether you need a different bell housing or not depends on what you already have and what trans you're going to (I'd bet you have an SM420 bell with a plate adapter there now). I have at least one extra cast iron bell housing for a Chevy available if you end up needing one. Have to measure it and see what trans it's for though (I think for SM420 also). After that you'll need to get the driveshafts lengthened/shortened. Both these transmissions work great with a V8.
To go to a Toyota 4-sp requires a few far more expensive parts; specifically a adapter bell housing. $400-500 used is the going rate IIRC. Given the cost vs. benefits of a Toyota trans vs. a SM420/465 I'd recommend the SM4xx trans. Unless you get a non-USA Toy 4-sp or 5-sp (H41-4 sp/H55f-5 sp both have a 5:1 First gear) it's hardly worth the effort. I've seen complete SM420/3-sp T-case set-ups go for the cost of the adapter bell alone.
The other common option is an NV4500. Not quite as low as an SM4xx series trans but lower than either of the Toyota options plus it has an overdrive for the highway. It's also kinda pricey but there are a few more benefits compared to the other options...
I'd also recommend sticking with the stock rear axle for the time being. They're pretty stout as is. They can easily run a 35" tire if you're not too hard on the throttle (pinions are the "weak link" but you'll note that Woody runs stock stuff on his Cruiser). I'd also recommend running the truck in a fairly mild form (IE hold off on the lockers and big lift) and learn how to drive it. They will go FAR once you learn how to drive them.
HTH,
Nick