A modest proposal for discussion:
Senators should be chosen only from within the elected federal and provincial members of the Houses of Parliament. They should be nominated and elected to senate by our elected representatives in their respective houses (each provincial house voting for the seats allocated to their province along with the federal Parliament members), with at least one nomination from each government federal and provincial, and the choice to nominate more resting with the federal government. Each senator elected should then be replaced in their ridings by by-election in a timely manner thereafter - thus "stacking" the senate risks weakening the government's hold on power. This should encourage non-partisan nominations of respected opposition members when the governing party cannot afford to weaken their own count in the house.
I do not believe that such a program would require constitutional change; only the agreement of the federal government and those of the provinces that choose to participate.