Monthly
Mortgage: $1,020
Grocery: $400
Gas: $300*
Cell phone: $160
Energy Bill (all electric): $100
Car Insurance: $80
Internet: $60
Water: $20
The OP asked where to start. I always start by sorting expenses from high to low.
Housing: The OP says no options, but I would argue this is self-imposed because of the dogs. As a pet owner who at one time lived with 3 dogs and 2 cats, I know that the temptation can be to say that there's "no option" but to keep them, however that is not actually true. It's a choice. Perhaps the OP wants to stay the course, but I would acknowledge that pet ownership is a luxury good, not a necessity.
Grocery: Again, as others pointed out, a portion of this is undoubtedly for the large dogs. Again, that's a luxury, and should be accounted for as such.
Gas: This one doesn't scare me nearly as much because the OP says that some of it is reimbursed by work. So the more they drive, the more they get reimbursed. As long as OP has a reasonably fuel efficient car (which we already know is paid off, too) I might pass on this one until the car actually needs replacement or if the paid off car is worth at least $10,000. If so, that could make it worth trading in on a certified used Prius or something that may potentially make sense economically.
Cell phone: As was covered, this is a lot of money for two lines and obscene if it's for only one line. If the husband isn't really working or going anywhere, he doesn't need a fancy cell phone. Something like the basic $10 Republic Wireless phone plan may be sufficient. If T-Mobile coverage is sufficient in your area, you could do a plan with unlimited data and a high end phone and still only come up to $100 or so.
Energy: Seems fine to me; pass.
Car insurance: This doesn't seem bad to me either if it's for two cars, but no harm in shopping around.
Internet/water: Again, so cheap that it's hard to get much savings when you're down in such small dollar amounts.
Not listed: credit card interest. The OP doesn't say how much is being spent on interest for the carried balances on the credit cards but let's say it's $15,000 of debt at 15%. That's $187/month in interest. Pay off the debt and you get $187/month back.
So that's it. Where to start is easy: Go where the money is. Whatever you're spending the most on is what you devote some time to first. Pick one budget area and research the heck out of it for an entire week. Once satisifed, go down to the next item on the list and work on that for a week, and so on. When you get to the bottom of the list, go back to the top and start over again. It's a systematic continuous improvement loop.