I have worked in an IT company in Germany where we went from not wanting to hire people from abroad at all to trying full force, and back again.
Why do the companies not like to undergo with Visa sponsorship?
There are two things to consider here. There is visa sponsorship and there is relocation. If they want to hire someone who needs a visa and does not have it yet, they have to provide the paperwork to get you your visa.
There are two types of visa. A normal work visa, and a § 19a Blue Card visa for highly skilled workers. The blue card is easier to get and gives you more benefits as the employee.
Both of them require an invitation letter1, and the need to communicate with the local job agency so you can prove that they can't hire someone locally. The latter includes writing a job description that fits your profile, so that it is obvious they couldn't find someone local. They will also need to prepare your work contract in an English translation, because you probably don't speak German and don't understand a thing that's in the contract.
There are also a couple of documents that you might need in the original, before you go to the embassy. Those need to be shipped to you, international courier, and fast.
All of these things cost extra money that they don't need to pay if they hire locally.
Once you have secured the visa, there are things that make sense for them to help with, but many companies don't. You need to find an apartment in a country you have never been to and don't speak the language of. You need to get registered, you need to go to the Auslaenderbehoerde a couple of times to get everything sorted out. You might need to redo your driving licence or get it transcribed. You need to buy furniture, make a phone contract, get insurances. Being an expat is hard work. And you need to come to the country in the first place. Maybe you're bringing a family, maybe you're bringing all your furniture. Someone needs to pay for that.
Some companies do that happily, because they see that extra 5 to 10k Euros as well invested so you can start motivated and without being super stressed about all the stuff you need to take care of in this strange environment. Others can't or don't want to spend that money. It happens.
In addition, there is also the cultural question. How many people in the company speak English. How international is it already. Can they realistically provide you with training for German. Do they have someone that can mentor you in all things Germany.
There is a massive shortage in skilled IT workers (and other areas) in Germany, but on the whole a lot of smaller companies simply don't have the knowledge to provide either of these two things, and they don't see the potential benefits of gaining that knowledge.
What can I offer to the company in my interview in order to encourage them to hire me?
I don't think you can change a company's mind easily. If you are an outstanding candidate, and you can prove that, you might be able to impress them, but if they don't want to hire people from abroad, you will be out of luck most likely. I believe it's more realistic you'll encounter more companies that have simply never thought about it, and are afraid of the risks, or the extra work that comes with it. If you impress those companies, there should be a chance to get in.
1) This is all unless you are from a country that can get visa-free Schengen entry, like the US or Canada. For a blue card you do not need to apply in an embassy in that case. You could come to Germany on your regular visa-free passport, and apply with your work contract directly at Auslaenderbehoerde. It will take a month, and you are not allowed to work until you have the physical Aufenthaltstitel card (or paper sticker in your passport) in your hand, but you don't need to go back. We tried getting the German embassy in Boston to do a Blue Card, and it was near impossible. They didn't know how it worked. Coming to Germany first is easier for that case.