We had a border collie, and a cat. The dog was the 'proper' type- she was born on a farm in Wales, and as youngster her sheep dog instincts would be liable to kick in- I'll never forget the day she attempted to herd up some toddlers in heaton park, to the great irritation of all concerned.
Initially there was a bit of a fracas when introductions were made, but border collies are generally very bright- and she learned pretty quickly that every time there was a fight, the smaller, faster cat, and it's penchant for jumping on tables and sideboards, invariably escaped the situation with more of it's dignity intact. She gave up in the end, and a truce was called. :)