Why Ctrl+P menu would be different, and no "Bone" option
That is referred to as a context menu, the available options vary depending on the active item that the action will be performed on. The active object is the one that will become the parent of the remaining selection, it can usually be identified by being highlighted in a lighter colour that the other selected objects.

In your first example you are parenting to an armature.

In the second example you are parenting to a mesh object (that is why you get the vertex parent options).

If you are parenting to a curve object you get curve options.



Parenting to a lattice you get lattice options.



While if you parent to an empty or metaball object you only get simple object parenting options.