So what is so great about House Tully?
In Game of Thrones, there is a complex hierarchy of Great and Lesser Houses, the most important of which are rulers over the various territories of Westeros (the Seven Kingdoms). At the time that Petyr Baelish makes this comment, House Tully is a Great House in control of the Riverlands.
At the time Frey's are a more minor noble house, indeed a vassal to House Tully - definitely a tier lower in importance. The Freys have pledged to serve the Lord of the Riverlands. As well as this hierarchy, Walder Frey is also noted by many people to be rather lacking in courage and loyalty - only joining in the battle that led to Robert Baratheon's rise to power at the last minute when it was clear he was going to win. This led to him having the nickname "the Late Walder Frey"
So Petyr is just observing what many people would consider a truth, that a marriage between a Frey and a Tully would be advantageous to the Frey's.
If you've not watched S1E09 "Baelor" yet, you shouldn't read the following spoiler:
This is also why the promise of Rob Stark to marry a Frey was the price that Walder Frey asked when the Stark army needed to cross the river. Rob as heir to the Ed Stark and future Lord of Winterfell was definitely a match worth making.