The German tax system is said to be complicated, but if you keep your business simple, it's usually not that much of a problem. The tax that will most interest you is the income tax (as a natural person). There's a difference between the tax rate and the effective tax you pay. You can see this at this image (pink = effective): http://upload.wikimedia.org/wikipedia/de/a/ac/EStTarif.PNG
If you run your business as a freelancer, you will most often have no trouble with the tax stuff.
If you want to incorporate we just got a reformed company law that gives us the "Unternehmergesellschaft." It's like a LLC oder Ltd., you can start it with 1 EUR and it's made esp. for startups. You have to accumulate 25% of your profits until you reach 25,000 EUR and become a "real" limited liability comp. (here GmbH). Foreigners can incorporate, too. Taxation is the "Koerperschaftssteuer" (corporation tax) which is flat 15%, then you have the local "Gewerbesteuer" (business tax) which (in Berlin) costs you also around 15%. Dividends are taxed flat with 25%.
If you don't have good advisors you pay a bit more taxes with a company than as a natural person alone, but you have the limited liability, you can more easily hand out shares to investors, have more possibilities with financing, a.s.o.
"[5] A friend who started a company in Germany told me they do care about the paperwork there, and that there's more of it. Which helps explain why there are not more startups in Germany."
We still have a lot of "rule compliance costs", esp. when a company has employees, but you can hack this. In the worst case you just source this paper work out. The problem is more that Germany lost its startup-mentality. The last time we were a real startup country is 100 years ago.
In the times of the German Economic Miracle there must have been a great startup-mentality here. That has been roughly 50 years ago.
And i'll throw Karlsruhe into the pot. It's called the internet capital of Germany, has lots of companies (especially web companies) and one of the best universities for computer science (and other technical fields). Living costs are relativly low.
If you want to incorporate we just got a reformed company law that gives us the "Unternehmergesellschaft." It's like a LLC oder Ltd., you can start it with 1 EUR and it's made esp. for startups. You have to accumulate 25% of your profits until you reach 25,000 EUR and become a "real" limited liability comp. (here GmbH). Foreigners can incorporate, too. Taxation is the "Koerperschaftssteuer" (corporation tax) which is flat 15%, then you have the local "Gewerbesteuer" (business tax) which (in Berlin) costs you also around 15%. Dividends are taxed flat with 25%. If you don't have good advisors you pay a bit more taxes with a company than as a natural person alone, but you have the limited liability, you can more easily hand out shares to investors, have more possibilities with financing, a.s.o.
Some more info there: http://en.wikipedia.org/wiki/Taxation_in_Germany