The teams were created 60-80 years before there even was a CFL. When the league was formed, the names were kept as they were.
Ottawa's Rough Riders were named for the loggers who worked on the Ottawa River, and Saskatchewan's were named for (I believe) the unit that Teddy Roosevelt led in the Spanish-American War, as there were some Canadians in the regiment.
I think I read somewhere that Ottawa changed it's name (I think it might have even been to the Senators), during which time Saskatchewan's team was created.