Not all fiber is equivalent. The fiber in legumes tends to be highly fermentable, and provide far more in the way of health benefits than the fiber in vegetables such as broccoli.
Lentils are pretty much nature's perfect food when considering cost, protein and fiber content. Additionally, lentils are low in methionine. I don't put much stock in methionine restriction for human longevity, it does work in rodents, so if you want to be a guinea pig (couldn't resist) they're good in that respect too.
Eggs are also excellent for their high essential fatty acid content, and this may sound counter-intuitive but if you eat a lot of beans dietary cholesterol is actually beneficial. High quality eggs are also a really good source of vitamins E and D.
Finally, though they're unfortunately not so cheap, hemp seeds provide you with both omega-3 and omega-6 fatty acids and minerals. A mix of sunflower or pumpkin seeds and chia seeds works well and is cheaper if you're optimizing for cost.
The only vitamin that I think is worth supplementing is niacin. Niacin has been shown to increase BDNF levels in animals which can help with mood and memory formation, and it has also been shown to increase lifespan by 10-15%. For people who don't go outside and don't consume much milk vitamin D might also be a good idea.