Getting a ship of the line is easy if you know how to do it. This is probably explained in that guide someone linked to, but I have a couple minutes, so I might as well describe my method.
The best era seems to be 1660. In my time, I have gotten fleets of six SOL's within just a few months. I've seen SOL's escorted by Large Frigates, and I even saw two SOL's sailing together. THAT was a big prize.
First of all, you have to be pretty good at land battles. What I like to do is sail around the Nevis/St Kitts area, looting as many non-English ships as I can. I'll get some promotions, but I'll also be able to recruit an insanely large crew. I'll keep a few captured cargo ships in order to carry all the new men.
Once I have about 300-400 men, I'll start sailing clockwise around the Caribbean, capturing EVERY SINGLE Spanish port and converting it to English. It's difficult at first, but once you have a good momentum going, it gets easy. You'll get some crazy mad gold this way, too.
Just leave two ports to the Spanish, so that Raymondo and Montalban have a place to hang out. This whole "port-conversion" thing will take a few years, but it's worth it.
Now that almost the entire Caribbean is English, head back to St Kitts/Nevis area. These ports should be super-wealthy and quite large by now. Every port in this area (including Montserrat and Martinique) should be converted to English. Now, just start looting the English ships like CRAZY. Take out every English ship you see. Sink them, keep them, whatever. Just make sure they go down.
Pretty soon, the English will be sending lots and lots of warships out. Just keep sinking everything you see. Soon, you'll be seeing SOL's all over the place.
When I do this, I find that SOL's show up when I don't even WANT them. lol I'm like, "Dang, I've already got like five of them. Screw it."
And it is my opinion that the Ship of the Line is THE best ship. Hands down. It's not even a matter of preference. If you prefer the Sloop of War or the Brig ships, you are WRONG. You're in denial. People that say the Ship of the Line sucks usually just say that because they've never gotten one.
It has 48 cannons and it's still rather maneuverable. Just keep a sloop in your fleet in case you have to chase a pinnace. I usually keep a SOL as my flag ship, I get it fully upgraded, and I name it the "Dauntless". Then I'll take out Raymondo/Montalban, knock out all the famous pirates, find all the treasures and lost cities, marry me a nice Spanish gal, and I'm good to go.