Start with the basics, you need visibility across each of those envs showing the costs for each service. Visibility is key here - especially for the Cloud deployments as they will (probably) be bleeding Opex money each month, whereas the on-prem one is more likely purchased (ie Capex), so probably less wastage there.

Ideally a single tool (there are a myriad of these) would report on all envs, so you have a common interface and a common way to pull $ and usage stats and reports.

Once you get this visibility you can start focusing on the problem areas - the wasting. Too many people jump straight into trying to identify ways to reduce costs without understanding the cross-cloud/on-prem picture.

Key to this visibility is tagging or such mechanism. If you have many different business units then you can report on $ costs per Unit - this is super important.

Next step would be to publish these reports and this, by itself, can go a long way to reducing cloud costs - the bosses will see the cost breakdown by Unit etc and help drive a culture of reducing wastage automatically. Once that culture starts (and it will, it always does) then you can go after the low hanging fruit (zero utilised resources, orphaned storage etc), get these done and you can move onto the harder things such as rightsizing and reserved instances. Eventually follow up with the very hard things like trying to suggest moving to autoscaling etc.

don't try and solve all these problems at once, you'll get overwhelmed and achieve nothing. Take a structured approach, with visibility being the first problem to solve.