The claim is based on Srimad Bhagwatam (SB 12.13.16) where Shiva is said to be the best of Vaishnavas.
However, what we need to be very clear is that the term Vaishnava here strictly means one who adores and meditates on Vishnu. It has nothing to do with being a devotee of Vishnu in the modern sectarian sense of Vaishnavism or subscribing to any theological doctrine of Vaishnavism.
Another verse that can be found in Bhagwatam relating to the same is 4.3.23 where Shiva tells Sati that he worships Vasudeva. Vasudeva here is Krishna/Vishnu in the form of the supreme Brahmana or vice versa as is evident from the preceding verse.
Harivamsa Chapter 90 has Mahadeva's stuti to Vasudeva, adoring him as Ishwara.
By these, it is evident that Bhagwan Shiva adores and meditates on Vishnu as Prabrahman. However, what needs to be clear is also that this should not be compared to the meditation or devotion that is present among us mortals. Shiva and Vishnu are the supreme Saguna manifestations of Brahman as Ishvara.
As is the devotion of Shiva to Vishnu/Krishna when they are seen as Ishwara Swarup of Brahman, same is the devotion of Krishna/Vishnu to Shiva when he is seen as Ishwara.
Anushasana Parva (MBH, KMG CLX) is the recitation of Vasudeva Krishna to Yudhishthira where he says, "O king, listen to me as I recite to you that Sata-rudriya which I repeat; with restrained senses, every morning after rising from bed" and then sings the glories of Shankara as Ishwara.
Drona Vadha Parva (MBH, KMG, CCII) Vyasa recites to Arjuna that he has seen "seen Sankara, that First cause from which have sprung the Prajapatis".
Harivamsa (Chapter. 74) has Shri Krishna's Stuti to Rudra Mahadeva along with the mention of installation of a Shivalinga by Krishna called "Bilvodakeshwara".
In the same Itihasa, Mahabharata or Harivamsa, we have alternating adoration and stutis of Shiva to Vasudeva and Vasudeva to Shiva. The same is the case with even Rigveda where both Rudra and Vishnu are praised as supreme forms of Ishwara.
Rigveda 1.156.2, “He who presents (offerings) to Viṣṇu, the ancient, the creator, the recent, the self-born; he who celebrates the great birth of that mighty one; he verily possessed of abundance, attains (the station) that is to be sought (by all).”
Rigveda 2.33.9, "(Firm) with strong limbs, assuming many forms fierce, and tawny-coloured, he shines with brilliant golden ornaments; vigour is inseparable from Rudra, the supreme ruler and lord of this world.” In the next verse, 2.33.10 Rudra is said to be the preserver of the world.
Conclusion: Both Shiva and Krishna/Vishnu being Ishvara in the complete sense and knower of Parabrahman as well as of each other's Ishwaratva, glorify, adore and meditate on each other. The same with Rishis who, on seeing both as supreme Ishwara and forms of the same Parabrahman (even saying form of Parabrahman is fallacy since there is no difference between them and Parabrahman yet, for simplicity..), sing praises of both as supreme. There is neither conflict nor contradiction here.
Unless ofcourse you want to go out on the quest to show one supreme over the other, which will lead to only headache and choicest of contorted interpretations.