I have to say that I was rather lucky:
1) In my first career (~50 missions) @ about mission 45 I saw my first capital ship and sank it with my XXI. It was an escort carrier
2) In my second career (22 missions so far), in the 2nd mission

I was assigned to the grid of Scapa Flow. Surprise-surprise, I went in, found a stationary Revenge Battleship and sank it with a salvo of my last three topedoes. That was with a Typ IIA
3) In the same (second career) after 20 missions I finally transfered to La Spezia. After my partol to the assigned grid I went with my IXB for a harbour raid in Valetta, sank 2 DDs and went out ~50 kms...only to find a big task force of 5-6 DDs plus Neson BB plus Revenge

But I couldn't get close to them. DDs were all over me.
As I read in the forum, the Med looks very promising for capitel ships encounters, especially near the staits of Gibraltar.
All these encounters were out of pure luck. I do not use RuB or Improved Convoys mod.
If you really want to see a capital ship, I would suggest that you search for old topics. Some people have already posted what is scripted in the campaign with specific dates and places where BBs hang around...