I've got some pretty good deals from Iceland air into Glasgow and Frankfurt. You have to stop off in Iceland though, but it is a neat stopover. They take you to a hot spring.
Was the flight crowded? They used to be on that airline. Then Loftleidir, that airline was very popular with young backpackers back in the 1970s. Then, the IATA forced the same rates on all members and only members could fly direct across the Atlantic. Loftleidir didn't belong to the IATA and offered lower fares and stopped in Reykjavik in lieu of direct flight. On one of their flights we unloaded a large fish as part of the crew luggage. Broke all kinds of laws with that.
Yes, like Edo says, IcelandAir could be one of the cheapest if you don´t mind silly, nonsense itineraries and long hours in airport halls. But having said that, those views when approaching Reijavik are just one of the most beautiful things I have ever seen. Also taking off in the middle of a terrible snow storm can be an additional emotion for the trip, if you go in the winter. Overall, it is a good airline, and great, cheaper service. Regards
I read in AW&ST that a Southwest Airlines type start-up was going to start trans-atlantic service in near future. But I could not locate a reference. Other than that Aer Lingus has some pretty good deals to Dublin and from there you can fly really low cost (occasionally free) on Easyjet or Ryan to other locations in Europe.