I liked Koln when I went there, was around Christmas and they had all the proper German christmas markets.
Inter-railing is the way to do it, had quite a few friends do that, although my brother just got back from 2 weeks of just cycling around France.
I also liked Bordeaux, was quite a cool city but that was over 10 years ago I was there much has probably changed.