O'Shea started his rugby playing career at Terenure College, where he won the Leinster Schools Rugby Senior Cup in 1991. He briefly represented his university UCD before leaving in 1992. Upon leaving, he joined Lansdowne, and soon became a regular starter at fullback in the 1st XV. He was selected for provincial side Leinster in 1993, where in 1994 he helped Leinster secure their first Irish Interprovincial Rugby Championship title since 1984, despite the title being shared. He scored Leinster's first ever try in a professional European tournament, scoring against Italian side Milan in the inaugural Heineken Cup. Leinster topped their pool with a win over Pontypridd, but failed to progress past the semi-finals where they were defeated by Cardiff 23–14.