TCP traceroute works fine but not UDP

I believe you are referring to these utilities:

http://www.vdberg.org/~richard/tcpping.html

http://michael.toren.net/code/tcptraceroute/

Since tcpping requires tcptraceroute, I'll start with tcptraceroute.

The author of tcptraceroute states that unlike a traditional traceroute, "By sending out TCP SYN packets instead of UDP or ICMP ECHO packets, tcptraceroute is able to bypass the most common firewall filters."

Further: It is worth noting that tcptraceroute never completely establishes a TCP connection with the destination host.

So, tcptraceroute does not measure the time it takes to complete the three-way handshake because that never happens. It measures the time from the initial SYN to the SYN/ACK. This is sometimes referred to as a half-open connection scan.

From the nmap manpage:

          This technique is often referred to as half-open scanning,
          because you don’t open a full TCP connection. You send a SYN
          packet, as if you are going to open a real connection and then
          wait for a response. A SYN/ACK indicates the port is listening
          (open), while a RST (reset) is indicative of a non-listener. If
          no response is received after several retransmissions, the port
          is marked as filtered. The port is also marked filtered if an
          ICMP unreachable error (type 3, code 1,2, 3, 9, 10, or 13) is
          received.

As to your packet size question, the above description also has the answer. Since tcptraceroute sends a standard SYN packet, it should be a small packet, perhaps 64 bytes.

ICMP messages are still IP packets. Traceroute uses ECHO Request (ICMP type 8) by default on Unix and Windows with incrementing TTLs, logging the sending address of each Time Exceeded (Type 11) message it gets back from the hops along the route. (cf: http://en.wikipedia.org/wiki/Internet_Control_Message_Protocol)

This is the 'correct' way to do it, but you can run in to problems if some of the systems on the route drop or differently handle ICMP traffic.

Some implementations of traceroute (on Linux for example) have -T and -U options for switching to TCP/UDP instead (and a following -p argument to specify a destination port). This is useful for more closely simulating real traffic, which might get you a more accurate result in some cases.

I suspect the OSX implementation defaults to UDP for that reason, but I can't say for sure. You might find a switch to use ICMP instead.