We can get Cheddar here, and bring back and freeze Red Leicester and Double Gloucester. If you defrost these faily slowly, they keep their original consistency (give or take). Cathedral City is best, as it is wrapped in Britain and remains fresh, whereas normally imported Cheddar is often starting to go moldy.
Out of the more 'local' cheeses, we like Old Amsterdam, which though crumbly has a rich taste not unlike Cheddar, and the unpronouncable Südtiroler Bergbauernkäse, which comes from German-speaking Italy (the South Tyrol). Several Swiss cheeses are nice, but I am always a tad wary of using unpasteurised milk. Still, haven't snuffed it from eating such cheese yet.
Also like blue cheese, but never understood why it doesn't make you ill, as it is only really moldy cheese anyway.