Autonomous robots are agents with physical bodies that share our environment. We test the hypothesis that physical embodiment has a measurable effect on performance and perception of social interactions. Acceptance of this hypothesis would suggest fundamental differences between virtual agents and robots from a social standpoint and have significant implications for human-robot interaction. We measure task performance and perception of a robot's social abilities in a structured, but open-ended task based on the towers of Hanoi puzzle. Our experiment compares aspects of embodiment by evaluating: (1) the difference between a physical robot and simulated one; (2) the effect of physical presence through a co-located robot versus a remote tele-present robot. We present initial data from a pilot study with 13 participants showing surprising differences in perception of remote physical robot and simulated agents attention to task, and task enjoyment. We posit future directions for evaluating the impact on task performance.