I found the reason for the error. When I move the proto files to the proto/ directory, I need to rerun the protoc tool to regenerate the py files:
python -m grpc_tools.protoc -I=. --python_out=. --pyi_out=. --grpc_python_out=. ./proto/service.proto
This way the generated py files will have the right import paths. The original server script in the tutorial would work without any modification.