This is a technical answer for the US. As a research administrator, I have submitted more than 100 applications for Computer Scientists at a world-class university in the last 6 years. I have successfully justified tens of millions of dollars across various fields of CS-- data science, AI, HCI, CNS, theory, etc. I have applied for funding to about 15 federal sponsors and dozens of non-federal ones including Silicon Valley. I hope to draw some distinctions between the CS and more classical math tracks, but please know that some of what applies to CS applies to math too; however my direct experience is mostly with CS and not math (which does have less funding overall). Lessons that I impart among all new faculty (and even some senior folks):
Applications to federal sponsors are no longer based on one person's research. Teams and centers are the new normal. If you want to go solo, there are still some options, e.g., NSF has the CISE Core Programs (our theory folks tend to fall under CCF, primarily under AF "Algorithmic Foundations"). However, NIH has nearly eliminated the solo R01 project--interdisciplinary teams are nearly always more compelling unless you are applying for a small project (R03), or a class like DP2 that focuses on a single PI's research. The average age of getting an R01 as the PI (the basic independent research grant) is famously old -- mean 44 y.o., median 42 y.o. So this all being said, I find that my current CS folks (mostly AI and HCI at present) are always part of teams. They can cobble together millions of dollars over 5-10 funding sources as part of these teams. It's all about taking a small to middling chunk out a large project. It is possible that you have to contribute to a topic that you are less interested in, but often my folks work with hospitals who have may get 75% of the budget on the application. For us, 25% of a multi-million dollar application is still a lot of money for one project. My folks are almost always subcontracts or non-lead collaborators (i.e. "Co-PI" for NSF). I have someone who is a sub on DOD MURIs -- that is a lot of funding for the individual, but only a small percentage of a huge application. You have to figure out your niche; find people who will plug you into their projects. A junior PI can be very well-funded by playing a small role on other people's projects. In my institution, it is customary for senior faculty to give their name to a junior PI's project (i.e., senior PI is lead PI helping fund junior PI's work), and the senior PI prioritizes 1 month of supplemental salary for the junior PI as well as giving them a graduate student or postdoc.
Be sponsor independent. CS faculty tend to apply to NSF of course, but they also find ways to hook into various DOD sponsors, NIH, DOE, Census Bureau, really any agency with a solicitation, their skills are probably valued in some small way. Again, $50k here, $300k there, it all adds up. You have to figure out which agencies fund basic research and through what mechanisms. You can search for open solicitations across all of the US government on grants.gov. If you are interested in US gov't contracts, you want sam.gov. I suggest finding PIs in your institution who can tell you what they submit to. You can also look them up online to see some of what they have been awarded (often on their own websites). Funding is a relationships game. I know folks who are friendly with the Program Officer/Program Manager, and this is how they get their funding. They know when to apply; they know what the agency wants to see in applications. They write for this relationship and they get the funding. This is very common with DOD, DOE, and NASA; somewhat with NSF.
Unlike in the wet labs, funding in CS is based on paying higher salaries and low to no "other direct costs". We generally don't put computers on grants because too many projects run on them to spend time allocating percentages. Some faculty get cloud computing resources donated. We instead write $500k grants to fund our very large indirect cost rate as well as postdocs starting in the $70-75k range plus about 25% in fringe. That doesn't go very far. We want to compete with Silicon Valley, but we can't. This is the best we can do. This is actually about $20k above the NIH minimum for postdocs.
When considering building a lab, I tell my faculty to consider two types of resources in particular: money and their time/patience. I have a PI (HCI is the focus) right now with over a million dollars (NSF funding split over about 5 grants, non-lead on 4 of them). I have to help them figure out how to spend in two years. This PI has less than 5 years as an assistant professor, with 2 years under COVID. Their postdoc just got a new job; they have two graduate students in their lab, one is 90% funded by a fellowship. What are we going to do? I have told them to hire at least 2 postdocs, but I won't let them hire just anyone. The reason is that CS labs tend to be small, especially ones bent on theory. At my institution, the theory labs like intimate groups and PIs do not expand them even when they are funded. So I ask my PI how they handle bad relationships -- if they are willing to part ways with a bad hire. If they hire someone who is just passable, they will have mediocre results for two years (possibly a third), and will end up feeling drained by having to support a postdoc who is supposed to be helping relieve the leadership role. So what can we do then if we don't hire a middling postdoc? I ask them if they have colleagues with students or postdocs who they can support on their project. Maybe a graduate student in a theory group, perhaps an ML person, etc. We chip away at that funding with small percentages on different projects, and this is the essence of successful resource sharing in CS and theory groups that I have found.
So what I would do is go to NSF's award search and look into what projects are funded for what you are interested in. Look up the PI's websites and see if their proposals are released on their site (not super common, but happens). If you really want to look at a successful application, you can submit a FOIA request to read the proposal that was funded. [ETA: Some folks feel you should contact the PI first and ask if they will share the proposal. If they say no, then you can submit the FOIA. Many PIs will share when asked.] Pay attention to the directorate. Are your people applying to the traditional MPS (Mathematical and Physical Sciences) or are they getting their funding through CISE (Computer and Information Science and Engineering)? If you are interested in total dollars each directorate and program awards, that information is available as well. Hint: DMS (Division of Mathematical Sciences) is not where the money is at. I highly suggest finding a person whose work you admire, looking them up in the NSF award system and seeing if you can find someone on a big center (e.g., AI Institutes, STC) and do a FOIA request to see how that person was written into the application.
Try to strike a balance between doing what you love, which may come without a lot of funding, and being willing to do something you don't want to do for much more funding. Find a research administrator at your organization and ask for advice. To your point about theory being cheap; that's a lot of your problem. IHE's (institutions of higher education) fund 9-month appointments for the PIs; they do their thing during the year; maybe in time hire a grad or two with startup funds, and they don't need a lot more than that. A bio-engineering PI would fail within months with a setup like that. The CS/math world is a much lower-stakes game (no judgement there; it just is). You don't have to deal with buying consumables, user fees, animals, human subjects, capital equipment, etc. etc.
Best of luck. The funding road is hard for everyone; even the top PIs. They spend more time thinking about funding their lab than you can possibly imagine. You are never "set".